|
| |
|
|
A055778
|
|
Number of 1's in the base-phi representation of n.
|
|
20
|
|
|
|
0, 1, 2, 2, 3, 3, 3, 2, 3, 4, 4, 5, 4, 4, 4, 5, 4, 4, 2, 3, 4, 4, 5, 5, 5, 4, 5, 6, 6, 7, 5, 5, 5, 6, 5, 5, 4, 5, 6, 6, 7, 5, 5, 5, 6, 5, 5, 2, 3, 4, 4, 5, 5, 5, 4, 5, 6, 6, 7, 6, 6, 6, 7, 6, 6, 4, 5, 6, 6, 7, 7, 7, 6, 7, 8, 8, 9, 6, 6, 6, 7, 6, 6, 5, 6, 7, 7, 8, 6, 6, 6, 7, 6, 6, 4, 5, 6, 6, 7, 7, 7, 6, 7, 8, 8
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
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
|
|
|
|
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
|
|
|
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
|
|
|
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
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
