Problem #235

Phinary representation
Public 04/30/15 10xp Math 100.0%

$\phi = \frac{1+\sqrt{5}}{2}$ is the golden ratio.
Any positive integer can be represented as a sum of powers of $\phi$ with integer exponents:
  • $ 1= \phi^0$
  • $ 2= \phi^1+\phi^{-2}$
  • $ 3= \phi^2+\phi^{-2}$
  • $ 4= \phi^2+\phi^0+\phi^{-2}$
  • $ 5= \phi^3+\phi^{-1}+\phi^{-4}$
  • $ 6= \phi^3+\phi^1+\phi^{-4}$
  • $ 7= \phi^4+\phi^{-4}$
  • $ 8= \phi^4+\phi^0+\phi^{-4}$
  • $ 9= \phi^4+\phi^1+\phi^{-2}+\phi^{-4}$
  • $10= \phi^4+\phi^2+\phi^{-2}+\phi^{-4}$
If we add the constraint that no exponent are consecutive, this representation is unique.
This representation is called the phinary representation of an integer.

For an integer n, we define M(n) as the sum of all exponents in its phinary representation: $$ M(641) = \sum{641_{\textrm{base-}\phi}} = \sum{\{13,9,7,5,2,0,-3,-11,-14\}} = 8$$ In the range $\left[1,10000000\right]$, find the minimun for M, the first integer which reaches the minimum, the maximum, and the first integer which reaches the maximum

Answer format: $M_{min},n_{min},M_{max},n_{max}$ // -17,77,8,46 for the range $\left[1,100\right]$

[My timing: 10 sec]

P.S:
Thanks to sinan for his suggestions which made this problem more interesting.



You need to be a member to keep track of your progress.
Register


Time may end, but hope will last forever.

Other Challenge Sites

Contact

elasolova
[64][103][109][97][105][108][46][99][111][109]