login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A055778 Number of 1's in the base-phi representation of n. 20

%I #88 May 09 2023 08:55:21

%S 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,

%T 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,

%U 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

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

%C Uses greedy algorithm (start with largest possible power of phi, then work downward) - see pseudo-code below.

%C 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

%C From _Michel Dekking_, Feb 06 2021: (Start)

%C Here is a proof that there are infinitely n many such that A007895(n) = a(n).

%C Let F(n) = A000045(n) be the n-th Fibonacci number, and let L(n) = A000032(n) be the n-th Lucas number.

%C Then a(L(2k)) = 2, since L(2k) = phi^(2k) + phi^(-2k), where phi is the golden ratio.

%C 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.

%C (End)

%C 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

%C 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

%H Carmine Suriano, <a href="/A055778/b055778.txt">Table of n, a(n) for n = 0..5000</a>

%H Michel Dekking, <a href="https://arxiv.org/abs/2003.14125">Points of increase of the sum of digits function of the base phi expansion</a>, arXiv:2003.14125 [math.CO], 2020.

%H F. Michel Dekking, <a href="https://doi.org/10.1016/j.tcs.2021.01.011">The sum of digits functions of the Zeckendorf and the base phi expansions</a>, Theoretical Computer Science, 2021.

%H Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/phigits.html">Using Powers of Phi to represent Integers (Base Phi)</a> (inspiration for this sequence).

%H Jeffrey Shallit, <a href="https://arxiv.org/abs/2305.02672">Proving Properties of phi-Representations with the Walnut Theorem-Prover</a>, arXiv:2305.02672 [math.NT], 2023.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PhiNumberSystem.html">Phi Number System</a>

%F 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

%F a(n) <= (A190796(n) + 1)/2. - _Charles R Greathouse IV_, Apr 21 2023

%e The phi-expansions for n<=15 are:

%e n phi-rep(n) a(n)

%e 0 0. 0

%e 1 1. 1

%e 2 10.01 2

%e 3 100.01 2

%e 4 101.01 3

%e 5 1000.1001 3

%e 6 1010.0001 3

%e 7 10000.0001 2

%e 8 10001.0001 3

%e 9 10010.0101 4

%e 10 10100.0101 4

%e 11 10101.0101 5

%e 12 100000.101001 4

%e 13 100010.001001 4

%e 14 100100.001001 4

%e 15 100101.001001 5

%e - _Joerg Arndt_, Jan 30 2012

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

%o (Pseudo-code from _Henry Bottomley_, Aug 04 2000):

%o 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;

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

%Y Cf. A001622.

%K base,easy,nonn

%O 0,3

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

%E More terms from _Henry Bottomley_, Aug 04 2000

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 12:59 EDT 2024. Contains 371254 sequences. (Running on oeis4.)