Nearest polygonal number def nearest_polygonal_number(n, s): Any positive integer s > 2 defines an infinite sequence of s-gonal numbers whose i:th element is given by the formula ((s-2)i2 - (s-4)i)/2, as explained on the Wikipedia page "Polygonal Number". In this formula, positions start from 1, not 0, and we use the letter i to denote the position since we will be using the letter n for something else. For example, the sequence of "octagonal numbers" that springs forth from s = 8 starts with 1, 8, 21, 40, 65, 96, 133, 176... Given the number of sides s and an arbitrary integer n, this function should return the s-gonal integer closest to n. If n falls exactly halfway between two s-gonal numbers, return the smaller one. As you can see from the last row of the previous table, this function must be efficient even for gargantuan values of n. The simplest way to make this function efficient is to harness the power of repeated halving to pull your wagon with a clever application of binary search. Start with two integers a and b wide enough that they satisfy a<=i<=b for the currently unknown position i that the nearest polygonal number is stored in. (Just initialize these as a=1 and b=2, and keep squaring b until the s-gonal number in that position gets too big. It's not like these initial bounds need to be accurate.) From there, compute the midpoint position (a+b)//2, and look at the element in that position. Depending on how that midpoint element compares to n, bring either b or a to the midpoint position. Continue this until the gap has become small enough so that b-a<2, at which point one last comparison tells you the correct answer.
Nearest polygonal number
def nearest_polygonal_number(n, s):
Any positive integer s > 2 defines an infinite sequence of s-gonal numbers whose i:th element is given by the formula ((s-2)i2 - (s-4)i)/2, as explained on the Wikipedia page "Polygonal Number". In this formula, positions start from 1, not 0, and we use the letter i to denote the position since we will be using the letter n for something else. For example, the sequence of "octagonal numbers" that springs forth from s = 8 starts with 1, 8, 21, 40, 65, 96, 133, 176...
Given the number of sides s and an arbitrary integer n, this function should return the s-gonal integer closest to n. If n falls exactly halfway between two s-gonal numbers, return the smaller one.
As you can see from the last row of the previous table, this function must be efficient even for gargantuan values of n. The simplest way to make this function efficient is to harness the power of repeated halving to pull your wagon with a clever application of binary search. Start with two
integers a and b wide enough that they satisfy a<=i<=b for the currently unknown position i that the nearest polygonal number is stored in. (Just initialize these as a=1 and b=2, and keep squaring b until the s-gonal number in that position gets too big. It's not like these initial bounds need to be accurate.) From there, compute the midpoint position (a+b)//2, and look at the element in that position. Depending on how that midpoint element compares to n, bring either b or a to the midpoint position. Continue this until the gap has become small enough so that b-a<2, at which point one last comparison tells you the correct answer.
Step by step
Solved in 2 steps with 3 images
