Project Euler 473 - Phigital number base

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

Thought Process

This problem was very hard for me, I could understand the maths but struggled a lot to implement my solution.

From prior knowledge, I know that the golden ratio is highly linked to Fibonacci numbers, and I thought it would be smarter to work with Fibonacci numbers instead of decimals for precision issues (This did not end up going well for me as I still ended up have precision issues)

My idea was the following:

  1. Find all of the phigital palindromic numbers that only have two 1's in them, these are sort of the base cases because all possible numbers will be formed by some combination of these, hence I call them base phigital palindromic numbers (BPPN)

  2. Add my BPPN in every-way possible and see which ones form integers, I will call these my principal phigital palindromic numbers (PPPN)

  3. Add my PPPN in every allowed way possible and I should get all of the numbers

It seemed so simple in my head but wow it took me a while to implement a method that worked.

Following the fibonacci wiki page we get the identities (1) and (2)

Then I can derive an equation which will easily allow me to solve step 1 of my idea

Step 1 is solved, step 2 is not so difficult, just a simple double for loop will do the trick.

Step 3 was the tricky one, because I have to make sure that I am adding them at-least 1 digit apart to ensure uniqueness.

To this end I made a stack.

Each element in the stack looks like this: [a, [alist]] where a is a PPPN and alist is a list containing which digit BPPN it contains.

For example we would have [14, [2, 5]]

Like this as I went through my stack of PPPN's I had a way to check that I was not adding numbers than were only 1 digit apart! and voila the problem was solved (I wish)

After this I had massive precision errors, I got all cases up to 8*10^7 correct and LUCKILY there is a website (https://euler.stephan-brumme.com/473/) where I was able to do test cases and check where I was going wrong and identify my problems.

I tried my best to solve it a smart way but I just couldn't do it, I ended up using the decimal module and fixed my precision issues and it finally worked!

Interactive Code

Enter an integer (yourinput)

Code will output the sum of positive integers not exceeding yourinput whose phigital representation is palindromic