Project Euler 293 - Pseudo-Fortunate Numbers

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

Thought Process

One key note is If N is an admissible number and not a power of 2 then it must be a product of at-least 2 consecutive primes, therefore we only need primes up till the square root of 10^9, which is very easy to compute.

Note: Even better 2*3*5*...*23 * 29> 10^9, so actually you only need primes less than 23. It makes almost no difference for my algorithm which runs ~3 seconds either way

My idea was just to generate all the admissible numbers and then from them find the pseudo-Fortunate numbers from there, I was going to use Fermat primality testing to speed it up but it turns out the maximum pseudo-Fortunate number is only 131 so theres not much to check either way.

I'm quite proud of my method of my way to generate admissible numbers, because I used recursion and I feel like i'm becoming more confident on my use of recursion.

I use recursion to generate all admissible numbers

Takes 4 inputs, besides obvious limit, a brief explanation

  1. p - first prime to start with

  2. n - current number

  3. primes - list of primes

I want to add p*n as an admissible number, and I also want to add p*n_p

Have breaks set in place so it doesn't go over the limit and I don't go past the last prime.

admissible_numbers(2, 2, list_prime(10^(4.5)), 10^9) now generates all admissible numbers less than 10^9

Interactive Code

Enter a number (yourinput)

Code will output the sum of distinct pseudo-Fortunate numbers for admissible numbers N less than yourinput