OFFSET
0,3
COMMENTS
Uses greedy algorithm (start with largest possible power of phi, then work downward) - see pseudo-code below.
Conjecture: For all n, A007895(n) <= a(n). There is equality at 1, 7, 18, 19, 47, 48, 54, 123, 124, 130, 141, 142, 322, 323, 329, 340, 341, 369, 370, 376, 843, 844, 850, 861, 862, 890, 891, 897, 966, 967, 973, 984, 985, 2207, 2208, 2214, 2225, 2226, 2254, 2255, 2261, 2330, 2331, 2337, 2348, 2349, 2529, 2530, 2536, 2547, 2548, 2576, 2577, 2583, ... - Dale Gerdemann, Apr 01 2012
From Michel Dekking, Feb 06 2021: (Start)
Here is a proof that there are infinitely n many such that A007895(n) = a(n).
Let F(n) = A000045(n) be the n-th Fibonacci number, and let L(n) = A000032(n) be the n-th Lucas number.
Then a(L(2k)) = 2, since L(2k) = phi^(2k) + phi^(-2k), where phi is the golden ratio.
On the other hand, A007895(L(2k)) = 2, since L(n) = F(n+1) + F(n-1) for all n > 1. So for k>1 one has A007895(L(2k)) = a(L(2k)) = 2.
(End)
Gerdemann's conjecture above is true: we can run the Bellman-Ford algorithm to determine the lowest-weight path from the initial state to a final state in the weighted directed graph derived from the automaton "saka" in my paper cited below in the Links section, and verify that they all have nonnegative weight. - Jeffrey Shallit, May 07 2023
Furthermore, the set of n, in Zeckendorf representation, for which A007895(n) = a(n), is accepted by an 8-state finite automaton. - Jeffrey Shallit, May 08 2023
LINKS
Carmine Suriano, Table of n, a(n) for n = 0..5000
Michel Dekking, Points of increase of the sum of digits function of the base phi expansion, arXiv:2003.14125 [math.CO], 2020.
F. Michel Dekking, The sum of digits functions of the Zeckendorf and the base phi expansions, Theoretical Computer Science, 2021.
Ron Knott, Using Powers of Phi to represent Integers (Base Phi) (inspiration for this sequence).
Jeffrey Shallit, Proving Properties of phi-Representations with the Walnut Theorem-Prover, arXiv:2305.02672 [math.NT], 2023.
Eric Weisstein's World of Mathematics, Phi Number System
FORMULA
a(n) = delta(x), where x is the fixed point starting with (0,0) of the morphism (j,0)->(j,0)(j,1), (j,1)->(j,2)(j,3), (j,2)->(j+2,0)(j+2,1)(j+2,2), (j,3)->(j+1,3)(j+2,2)(j+1,3) for all natural numbers j, and delta is the decoration morphism (j,0)-> j,j+1, (j,1)-> j+2, (j,2)-> j+2,j+3, (j,3)-> j+3,j+3 for all natural numbers j. - Michel Dekking, Feb 06 2021
a(n) <= (A190796(n) + 1)/2. - Charles R Greathouse IV, Apr 21 2023
EXAMPLE
The phi-expansions for n<=15 are:
n phi-rep(n) a(n)
0 0. 0
1 1. 1
2 10.01 2
3 100.01 2
4 101.01 3
5 1000.1001 3
6 1010.0001 3
7 10000.0001 2
8 10001.0001 3
9 10010.0101 4
10 10100.0101 4
11 10101.0101 5
12 100000.101001 4
13 100010.001001 4
14 100100.001001 4
15 100101.001001 5
- Joerg Arndt, Jan 30 2012
MATHEMATICA
nn = 100; len = 2*Ceiling[Log[GoldenRatio, nn]]; Table[d = RealDigits[n, GoldenRatio, len]; Total[d[[1]]], {n, 0, nn}] (* T. D. Noe, May 20 2011 *)
PROG
(Pseudo-code from Henry Bottomley, Aug 04 2000):
constant (float): phi=(sqrt(5)+1)/2; function: lphi(x)=log(x)/log(phi); variable (float): rem=n; variable (integer): count=0; loop: while rem>0 {rem=rem-phi^floor[lphi(rem)]; count++; } result: return count;
CROSSREFS
KEYWORD
base,easy,nonn
AUTHOR
Robert Lozyniak (11(AT)onna.com), Jul 12 2000
EXTENSIONS
More terms from Henry Bottomley, Aug 04 2000
STATUS
approved