Project Euler 221 - Alexandrian Integers

Official link: https://projecteuler.net/problem=221

Thought Process

A google search will find you the OEIS sequence: https://oeis.org/A147811, which gives a nice formula for generating Alexandrian Integers, "The numbers are of the form p(p+d)(p+(p^2+1)/d), where d runs over divisors of p^2+1 and p runs over all positive integers.", below is a proof for this formula.

Now we can run p over the integers, calculate the divisors of p*p + 1 and find all the corresponding Alexandrian integers (We also note that we only need to calculate the Alexandrian integers for the first half of the divisors because if p*p - 1 = ab then A1 = p(p+a)(p+(p^2+1)/a) = p(p+a)(p+b) = p(p+b)(p+(p^2+1)/b) = A2)

However we must crucially note that they will not be generated in order!!

I trial and errored and found that generating 500,000 alexandrian integers using the above method gets the correct answer.

Interactive Code

No interactive code for this problem, my code is given below

Page updated

Google Sites

Report abuse