How do you determine if a number N is a Pentagonal Number?
Just yesterday, I decided to do a couple of problems from Project Euler. I hadn't been to the site in a long long time, but I was happy that I got through Problem 19 and Problem 43 in short order, but then I've temporarily hit a wall with Problem 44. The problem is phrased in terms of Pentagonal numbers and while working through it, I derived an interesting result that I'd like to share with you, namely "How do you efficiently test if a number is Pentagonal?".
Recall that a Pentagonal Number is a number N which is representable by a formula
where n is a Natural number. To test whether N is a Pentagonal Number, all we need to do is to solve the equation:
which is a simple quadratic and check if n is a Natural Number. That's pretty easy for humans to do when N is a small quantity but programming languages aren't very good with quadratic equations, so we need to do some pre-processing of the quadratic equation for them.
Simplifying the above equation, we get:
The roots of this are:
![n = \frac{1 \pm \sqrt{1 + 24N}}{6}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_smQVJwhTpNh3rVwab5mFwUk1uRfPj0Gpic5OPgsLOyNB5wm4NOeNiMagF8PElEO45TNiVCCHiVgPzr0pUim9yS5Wv2SZGIKpoBvo9MP8VgY95R67A74oZ9ZAXRor_xfHguXbTrHqrCZFCcWtdissokhxG8wYmdRIn4QQ=s0-d)
Let's analyze the first root:
![n = \frac{1 + \sqrt{1 + 24N}}{6}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_v1x4usrTuHfTnYVIYJxs4UsEWvWei4Qwk4PvTZ8Iya0LVL4Li_UJV7ypylsRsuRI2EdcYm_YECi1WgOBq9xJOkgDse3HXxpzuX4Z6RwSphDdvR0meMdwaW9aJlkTAzNgOY7sJr32J2Ux5WN5Gf_WAeA2i-q27VSg=s0-d)
Now, since n is a Natural number, 1 + sqrt(1 + 24N) should be divisible by 6. In more mathematical notation,
![1 + \sqrt{1 + 24N} = 0 \mod{6}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sA3eVp5LcnOpd2mEEier9jAGPGzEzJlV8Na4SZZAhvQDyqQmVuVjEGRzQLOf5i1gjuOsAd8Bs6NmlTio0qjm2D3SdRzDR5j5R2FDNJqZWsIesoeNX1fX6RtVdhMq281UEEVcdHqgeVGIokFx51Uva6GQ=s0-d)
(Note: Here I'm using the mathematical notation of mod rather than the CS notation of mod. The mod 6 at the end applies to both sides of the equation.)
Simple analysis would then indicate that
![\sqrt{1 + 24N} = 5 \mod{6}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uIZ86Vx2JP1xe2rIVVTWmmWjeoI-cLoIzvwE7Ik4FGgXXiHlCB8rTGNAGLOWZhy6cDw32bR4l8ekwQ14hSQb9y2vsM-PaCHB2yEo8qqR8HATvZQDsAIUCAkHRQXR_j4hExY2SwdBKoWnppNAc=s0-d)
Just checking the above condition is enough to determine if a number N is a non-generalized Pentagonal Number. But can we do better?
It is well known that the following property holds in modular arithmetic:
Applying the above property to square the previous equation results in:
or,![(\sqrt{1 + 24N})^2 \mod 6 = 25 \mod 6](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vS17xQ_qdBmQTud3nR4uObOlnvGilR8N_Gkp9Li3Nlo9UEkau_8P2mzbZ5TKoz2p8PNCNFButTXhPTFAXVQcd2oEhAfI2HpZUFDxxt_DzNxNk8QlSK0wJBOHhmtf-4JZ1u_giNeyl5iF4GRh1gWtatja7S3Yel2fw=s0-d)
or,![(1 + 24N) \mod 6 = 1 \mod 6](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tti-ex6p8JaeRleevnQwwb42tRIpFumCTObjRB0-S8W1TlyYM4KZpGEdyoUOFq857Qq6vOuWlb4ozcg2QVHlcOTSP4m09rhORljQYxWT1d4mX1yrk2Ux9WAJg5A6sY8JImxZEkFzg=s0-d)
or,![24N \mod 6 = 0 \mod 6](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vWK4krNBZUZzUaMlYRBHT7n0laB0N031f0phAr663D7R2WlpIbvKL04NyxRybRhSnWM8bCh7qD3Pp1ntm2tA95j9XsKg20OfFAEm5KrOtvKDEQF-EpLZiAnEsyNYm0fPM=s0-d)
The above constraint is always true, irrespective of the value of N. Therefore, the only constraints on testing if a number is Pentagonal is that 1 + 24 N must be a perfect square. A small caveat though is that we've used a squaring procedure to map x mod 6 to x^2 mod 6 - this mapping is not 1:1 since a squared number may have multiple roots in mod 6 space (indeed 1 mod 6 has two discrete square roots 1 mod 6 and 5 mod 6). What that means is that this test is actually necessary but not sufficient.
For numbers where (1 + 24 N) is a perfect square but sqrt(1 + 24 N) == 1 mod 6, the above squared equations are satisfied but they are not "normal" Pentagonal numbers. A quick glance will show that numbers which have sqrt(1 + 24 N) == 1 mod 6, when put into the formula for the root of the quadratic equation
(note the negative sign) will always yield a value that is 0 mod 6 thus guaranteeing an integral value for n (though negative in sign).
In other words, either
![1 - \sqrt{1 + 24 N} = 0 \mod 6](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_te-bH6o074rVDcqxUw6iFmTPPTZYhlseYonB5dPEdbIKgRwqus0uC2v31DQWDyy_oGimtuW9HoHHer7zJepZU2ZayNYYwyjbpDIMNkBUyHUBLznhpOjRavKwneEpN5GXmT7LipvDlEIPYzr3KS=s0-d)
or
always holds if (1 + 24 N) is a perfect square. Thus, we will always get an integral n (though not necessarily positive) as long as 1 + 24 N is a perfect square.
Therefore, in all cases, to test if a number is a Generalized Pentagonal Number, it is necessary and sufficient that (1 + 24 N) is a perfect square. If you want to stick to just non-Generalized Pentagonal numbers, then use the additional restriction that sqrt(1 + 24 N) mod 6 == 5. QED.
NOTE: A previous version of this post claimed the simpler test to be necessary and sufficient for non-Generalized Pentagonal Numbers. There was a flaw in the analysis and the post has been updated to indicate that the simpler test holds only for Generalized Pentagonal Numbers. Many thanks to Dave Evans for providing a detailed counterexample over email and apologies for the incorrect analysis and claim the first time around.
Recall that a Pentagonal Number is a number N which is representable by a formula
Simplifying the above equation, we get:
The roots of this are:
Let's analyze the first root:
Now, since n is a Natural number, 1 + sqrt(1 + 24N) should be divisible by 6. In more mathematical notation,
(Note: Here I'm using the mathematical notation of mod rather than the CS notation of mod. The mod 6 at the end applies to both sides of the equation.)
Simple analysis would then indicate that
Just checking the above condition is enough to determine if a number N is a non-generalized Pentagonal Number. But can we do better?
It is well known that the following property holds in modular arithmetic:
Applying the above property to square the previous equation results in:
or,
or,
or,
The above constraint is always true, irrespective of the value of N. Therefore, the only constraints on testing if a number is Pentagonal is that 1 + 24 N must be a perfect square. A small caveat though is that we've used a squaring procedure to map x mod 6 to x^2 mod 6 - this mapping is not 1:1 since a squared number may have multiple roots in mod 6 space (indeed 1 mod 6 has two discrete square roots 1 mod 6 and 5 mod 6). What that means is that this test is actually necessary but not sufficient.
For numbers where (1 + 24 N) is a perfect square but sqrt(1 + 24 N) == 1 mod 6, the above squared equations are satisfied but they are not "normal" Pentagonal numbers. A quick glance will show that numbers which have sqrt(1 + 24 N) == 1 mod 6, when put into the formula for the root of the quadratic equation
In other words, either
or
always holds if (1 + 24 N) is a perfect square. Thus, we will always get an integral n (though not necessarily positive) as long as 1 + 24 N is a perfect square.
Therefore, in all cases, to test if a number is a Generalized Pentagonal Number, it is necessary and sufficient that (1 + 24 N) is a perfect square. If you want to stick to just non-Generalized Pentagonal numbers, then use the additional restriction that sqrt(1 + 24 N) mod 6 == 5. QED.
NOTE: A previous version of this post claimed the simpler test to be necessary and sufficient for non-Generalized Pentagonal Numbers. There was a flaw in the analysis and the post has been updated to indicate that the simpler test holds only for Generalized Pentagonal Numbers. Many thanks to Dave Evans for providing a detailed counterexample over email and apologies for the incorrect analysis and claim the first time around.
This comment has been removed by the author.
ReplyDeletechakah...!
ReplyDeleted man ko gyapon kabalo!!!!!