Testing pentagonal numbers

The nth pentagonal quantity P_n is the variety of dots in diagrams like these under with n concentric pentagons.

We’ve the components

P_n = (3n² − n)/2

the place n is a optimistic integer. If n is an integer however not optimistic, the equation above defines a generalized pentagonal quantity.

In the event you’re given an n, you’ll be able to simply compute P_n. However suppose you’re given a big quantity x. How would you identify if it’s a pentagonal quantity? And if it’s a pentagonal quantity, how would you discover n such that x = P_n?

If

x = P_n = (3n² − n)/2

then we are able to remedy a quadratic equation for n:

n = (1 ± √(24x + 1))/6.

If 24x + 1 shouldn’t be an ideal sq., n shouldn’t be an integer and x shouldn’t be a pentagonal quantity, bizarre or generalized. For instance,

√(24 × 20260615 + 1)) = 22051.185…

and so 20260615 shouldn’t be a pentagonal quantity nor a generalized pentagonal quantity.

Now suppose

x = 170141183460469231731687303715884105727.

Is that this a pentagonal quantity? You may’t simply compute √(24x + 1) in floating level arithmetic as a result of the result’s a 20-digit quantity, and floating level quantity have 15 digits of precision, so you’ll be able to’t inform whether or not the result’s an integer.

Nevertheless, you’ll be able to compute

⌊√(24x + 1)⌋

with solely integer arithmetic utilizing the sqrt_floor perform from this submit.

def sqrt_floor(n):
    a = n
    b = (n + 1) // 2
    whereas b < a:
        a = b
        b = (a*a + n) // (2*a)
    return a

The next prints a optimistic quantity,

x = 2**127 - 1
y = 24*x + 1
r = sqrt_floor(y)
print(y - r**2)

which tells us y shouldn’t be an ideal sq..

Now suppose y is an ideal sq.. Then

(1 ± √(24x + 1))/6

is rational, does it should be an integer? The truth is it one, and just one, of the roots might be an integer. If

24x + 1 = r²

then r is congruent to ±1 mod 6 as a result of the left aspect is congruent to 1 mod 6. If r = 1 mod 6 then the smaller root is an integer, and if r = 5 mod 6 then the bigger root is an integer.

So if 24x + 1 = r², then x is a pentagonal quantity if r = 5 mod 6 and a generalized pentagonal quantity in any other case.

The perform pentagonal_index takes a quantity x and return n if x = P_n and None if no such n exists.

def pentagonal_index(x):
    y = 24*x + 1
    r = sqrt_floor(y)
    if r*r != y:
        return None
    if r % 6 == 5:
        return (1 + r) // 6
    else:
        return (1 - r) // 6

We are able to take a look at this with the next code.

P = lambda n: (3*n**2 - n) // 2
for n in [2, 3, -4, -5, 10**200]:
    assert(pentagonal_index(P(n)) == n)

Observe that P(10**200) is simply too massive to suit right into a float, however the code works nice. It is because we use integer division (//) all over the place. If we had mentioned

P = lambda n: (3*n**2 - n) / 2

the take a look at above would move for the small values of n however output

OverflowError: integer division end result too massive for a float

when it got here to n = 10²⁰⁰.

Associated posts