import random
import numpy as np


total_results = 10000000000000000000003
# we're X% off on our estimates, relative to the difference between the asked
# page and the total number of pages
error_size = 0.2
# we have a X% bias on our estimate
error_bias = -0.1

results_per_page = 10
total_pages = total_results // results_per_page


def give_me_page(page_number):
  # returns two numbers: number of results for this page and
  # estimated number of pages; if we're asking for a larger page (one we have
  # no results for), return -1, -1
  if page_number > total_pages:
    return -1, -1

  results_left = total_results - (page_number * results_per_page)
  results_on_page = results_per_page if results_left > results_per_page else \
      results_left

  difference = total_pages - page_number
  estimate = page_number + random.normalvariate(difference * (1 + error_bias), \
      difference * error_size)
  estimate = int(estimate * results_per_page)

  return results_on_page, estimate


def guess_page():
  p_current = 0
  results_on_page, estimate = give_me_page(p_current)
  total_steps = 1
  if results_on_page < results_per_page:
    return total_steps

  p_est = estimate // results_per_page

  while True:
    results_on_page, estimate = give_me_page(p_est)
    total_steps += 1
    if results_on_page != -1:
      if results_on_page < results_per_page:
        return total_steps
      else:
        p_current = p_est
        p_est = estimate // results_per_page
    else:
      p_est = (p_current + p_est) // 2


steps_list = [guess_page() for i in range(1000)]
print(np.mean(steps_list), np.std(steps_list))