A055778 Number of 1's in the base-phi representation of n.

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

Offset: 0

Author

Robert Lozyniak (11(AT)onna.com), Jul 12 2000

Keywords

• base
• easy
• nonn

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

Examples

			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
		

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

Crossrefs

See also A330037 = (a(n) mod 2).

Cf. A001622.

Programs

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 *)

Pseudocode

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; // Henry Bottomley, Aug 04 2000

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

Extensions

More terms from Henry Bottomley, Aug 04 2000