Bigint week

Both our tasks this week require us to use integers greater than 2^64. I used the Math::Bigint module to handle those.

Task 1:  Fortunate numbers

The definition of Fortunate numbers leads to the following basic algorithm for finding them:

• Loop over n = 1 to something big
• Calculate the product of the first n primes (pn)
• Loop over m = 2 to something else big
• Calculate pn + m and check if it's prime

People cleverer than me will have thought (or known) of a better way, but mine works and is easy to understand.

However, pn increases very steeply and pn(17) is the largest that will fit into 64 bits, so Bigint is needed to represent pn for larger ones.  And also, pn + m will be bigint-ish which makes it hard to determine its primality, but fortunately Math::Prime::Util can do that, though for very large numbers it's guessing a bit.

My algorithm finds the first 20 Fortunate numbers - confirmed by the OEIS - in a couple of seconds even on a slow processor.

However, it is not immediately obvious that there isn't example of, say m = 11, for some huge n that I didn't explore.

Task 2: Fibonacci related patterns

It is asserted that if you create a sequence where each term is the corresponding member of the Fibonacci series modulo n, for any n, the sequence is a repeating pattern.

Perl is really good at patterns, so I approached this as follows:

• Create the Fibonacci series up to a big number (big)
• Create a string by concatenating the members of the series, modulo n
• Loop over 2 to a medium-sized number - this is the length of the repeat, pp
• So the unit that (maybe) repeats comprises chars 0 to pp-1 of the string
• Make another string containing enough copies of the unit to be longer than big, and then truncate it to big characters
• We have a result if 'another string' is the same as 'string'.

In order to cope with n being more than 10, all the moduli are represented as a single character, eg for n=16 the usual 0-9A-F but then running through to Z and then a-z, so that the algorithm can cope with n up to 62.  Again, the larger members of the series (beyond the 94th) exceed the capacity of 64 bits, so Bigint is needed again.

And just to show that it works,  I set big to be 1000, pp to go up to 40, and it runs in a few seconds up to p(62), which is 30 as per the OEIS.

And there's always a however.  If the modulo sequence for some number, say, goes 01234012340123401234 ... 44 with the 5 character sequence repeating 200 times followed by 44, my algorithm will not catch that.  It could be that the repeat is 1001 characters long. But perhaps someone has proved that that won't happen - ie that there is an upper bound for the length of the repeat?