cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-7 of 7 results.

A007895 Number of terms in the Zeckendorf representation of n (write n as a sum of non-consecutive distinct Fibonacci numbers).

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 2, 2, 1, 2, 2, 2, 3, 1, 2, 2, 2, 3, 2, 3, 3, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 4, 4, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 4, 4, 2, 3, 3, 3, 4, 3, 4, 4, 3, 4, 4, 4, 5, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 2, 3, 3
Offset: 0

Views

Author

Felix Weinstein (wain(AT)ana.unibe.ch) and Clark Kimberling

Keywords

Comments

Also number of 0's (or B's) in the Wythoff representation of n -- see the Reble link. See also A135817 for references and links for the Wythoff representation for n >= 1. - Wolfdieter Lang, Jan 21 2008; N. J. A. Sloane, Jun 28 2008
Or, a(n) is the number of applications of Wythoff's B sequence A001950 needed in the unique Wythoff representation of n >= 1. E.g., 16 = A(B(A(A(B(1))))) = ABAAB = `10110`, hence a(16) = 2. - Wolfdieter Lang, Jan 21 2008
Let M(0) = 0, M(1) = 1 and for i > 0, M(i+1) = f(concatenation of M(j), j from 0 to i - 1) where f is the morphism f(k) = k + 1. Then the sequence is the concatenation of M(j) for j from 0 to infinity. - Claude Lenormand (claude.lenormand(AT)free.fr), Dec 16 2003
From Joerg Arndt, Nov 09 2012: (Start)
Let m be the number of parts in the listing of the compositions of n into odd parts as lists of parts in lexicographic order, a(k) = (n - length(composition(k)))/2 for all k < Fibonacci(n) and all n (see example).
Let m be the number of parts in the listing of the compositions of n into parts 1 and 2 as lists of parts in lexicographic order, a(k) = n - length(composition(k)) for all k < Fibonacci(n) and all n (see example).
A000120 gives the equivalent for (all) compositions. (End)
a(n) = A104324(n) - A213911(n); row lengths in A035516 and A035516. - Reinhard Zumkeller, Mar 10 2013
a(n) is also the minimum number of Fibonacci numbers which sum to n, regardless of adjacency or duplication. - Alan Worley, Apr 17 2015
This follows from the fact that the sequence is subadditive: a(n+m) <= a(n) + a(m) for nonnegative integers n,m. See Lemma 2.1 of the Stoll link. - Robert Israel, Apr 17 2015
From Michel Dekking, Mar 08 2020: (Start)
This sequence is a morphic sequence on an infinite alphabet, i.e., (a(n)) is a letter-to-letter projection of a fixed point of a morphism tau.
The alphabet is {0,1,...,j,...}X{0,1}, and tau is given by
tau((j,0)) = (j,0) (j+1,1),
tau((j,1)) = (j,0).
The letter-to-letter map is given by the projection on the first coordinate: (j,i)->j for i=0,1.
To prove this, note first that the second coordinate of the letters generates the infinite Fibonacci word = A003849 = 0100101001001....
This implies that for all n and j one has
|tau^n(j,0)| = F(n+2),
where |w| denotes the length of a word w, and (F(n)) = A000045 are the Fibonacci numbers.
Secondly, we need the following simple, but crucial observation. Let the Zeckendorf representation of n be Z(n) = A014417(n). For example,
Z(0) = 0, Z(1) = 1, Z(2) = 10, Z(3) = 100, Z(4) = 101, Z(5) = 1000.
From the unicity of the Zeckendorf representation it follows that for the positions i = 0,1,...,F(n)-1 one has
Z(F(n+1)+i) = 10...0 Z(i),
where zeros are added to Z(i) to give the total representation length n-1.
This gives for i = 0,1,...,F(n)-1 that
a(F(n+1)+i) = a(i) + 1.
From the first observation follows that the first F(n+1) letters of tau^n(j,0) are equal to tau^{n-1}(j,0), and the last F(n) letters of tau^n(j,0) are equal to tau^{n-1}(j+1,1) = tau^{n-2}(j+1,0).
Combining this with the second observation shows that the first coordinate of the fixed point of tau, starting from (0,0), gives (a(n)).
It is of course possible to obtain a morphism tau' on the natural numbers by changing the alphabet: (j,0)-> 2j (j,1)-> 2j+1, which yields the morphism
tau'(2j) = 2j, 2j+3, tau'(2j+1) = 2j.
The fixed point of tau' starting with 0 is
u = 03225254254472544747625...
The corresponding letter-to-letter map lambda is given by lambda(2j)=j, lambda(2j+1)= j. Then lambda(u) = (a(n)).
(End)

Examples

			a(46) = a(1 + 3 + 8 + 34) = 4.
From _Joerg Arndt_, Nov 09 2012: (Start)
Connection to the compositions of n into odd parts (see comment):
[ #]:  a(n)  composition into odd parts
[ 0]   [ 0]   1 1 1 1 1 1 1 1
[ 1]   [ 1]   1 1 1 1 1 3
[ 2]   [ 1]   1 1 1 1 3 1
[ 3]   [ 1]   1 1 1 3 1 1
[ 4]   [ 2]   1 1 1 5
[ 5]   [ 1]   1 1 3 1 1 1
[ 6]   [ 2]   1 1 3 3
[ 7]   [ 2]   1 1 5 1
[ 8]   [ 1]   1 3 1 1 1 1
[ 9]   [ 2]   1 3 1 3
[10]   [ 2]   1 3 3 1
[11]   [ 2]   1 5 1 1
[12]   [ 3]   1 7
[13]   [ 1]   3 1 1 1 1 1
[14]   [ 2]   3 1 1 3
[15]   [ 2]   3 1 3 1
[16]   [ 2]   3 3 1 1
[17]   [ 3]   3 5
[18]   [ 2]   5 1 1 1
[19]   [ 3]   5 3
[20]   [ 3]   7 1
Connection to the compositions of n into parts 1 or 2 (see comment):
[ #]:  a(n)  composition into parts 1 and 2
[ 0]   [0]   1 1 1 1 1 1 1
[ 1]   [1]   1 1 1 1 1 2
[ 2]   [1]   1 1 1 1 2 1
[ 3]   [1]   1 1 1 2 1 1
[ 4]   [2]   1 1 1 2 2
[ 5]   [1]   1 1 2 1 1 1
[ 6]   [2]   1 1 2 1 2
[ 7]   [2]   1 1 2 2 1
[ 8]   [1]   1 2 1 1 1 1
[ 9]   [2]   1 2 1 1 2
[10]   [2]   1 2 1 2 1
[11]   [2]   1 2 2 1 1
[12]   [3]   1 2 2 2
[13]   [1]   2 1 1 1 1 1
[14]   [2]   2 1 1 1 2
[15]   [2]   2 1 1 2 1
[16]   [2]   2 1 2 1 1
[17]   [3]   2 1 2 2
[18]   [2]   2 2 1 1 1
[19]   [3]   2 2 1 2
[20]   [3]   2 2 2 1
(End)
From _Michel Dekking_, Mar 08 2020: (Start)
The third iterate of the morphism tau generating this sequence:
      tau^3((0,0)) = (0,0)(1,1)(1,0)(1,0)(2,1)
= (a(0),0)(a(1),1)(a(2),0)(a(3),0)(a(4),1). (End)
		

References

  • Cornelius Gerrit Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Simon Stevin 29 (1952), 190-195.
  • F. Weinstein, The Fibonacci Partitions, preprint, 1995.
  • Édouard Zeckendorf, Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41, 179-182, 1972.

Crossrefs

Cf. A135817 (lengths of Wythoff representation), A135818 (number of 1's (or A's) in the Wythoff representation).
Record positions are in A027941.

Programs

  • Haskell
    a007895 = length . a035516_row  -- Reinhard Zumkeller, Mar 10 2013
    
  • Maple
    # With the following Maple program (not the best one), B(n) (n >= 1) yields the number of terms in the Zeckendorf representation of n.
    with(combinat): B := proc (n) local A, ct, m, j: A := proc (n) local i: for i while fibonacci(i) <= n do n-fibonacci(i) end do end proc: ct := 0; m := n: for j while 0 < A(m) do ct := ct+1: m := A(m) end do: ct+1 end proc: 0, seq(B(n), n = 1 .. 104);
    # Emeric Deutsch, Jul 05 2010
    N:= 1000: # to get a(n) for n <= N
    m:= ceil(log[(1+sqrt(5))/2](sqrt(5)*N)):
    Z:= Vector(m):
    a[0]:= 0:
    for n from 1 to N do
    if Z[1] = 0 then Z[1]:= 1; q:= 1;
    else Z[2]:= 1; Z[1]:= 0; q:= 2;
    fi;
    while Z[q+1] = 1 do
      Z[q]:= 0;
      Z[q+1]:= 0;
      Z[q+2]:= 1;
      q:= q+2;
    od:
    a[n]:= add(Z[i],i=1..m);
    od:
    seq(a[n],n=0..N); # Robert Israel, Apr 17 2015
    # alternative
    read("transforms") : # https://oeis.org/transforms.txt
    A007895 := proc(n)
        wt(A003714(n)) ;
    end proc:
    seq(A007895(n),n=0..10) ; # R. J. Mathar, Sep 22 2020
  • Mathematica
    zf[n_] := (k = 1; ff = {}; While[(fi = Fibonacci[k]) <= n, AppendTo[ff, fi]; k++]; Drop[ff, 1]); zeckRep[n_] := If[n == 0, 0, r = n; s = {}; fr = zf[n]; While[r > 0, lf = Last[fr]; If[lf <= r, r = r - lf; PrependTo[s, lf]]; fr = Drop[fr, -1]]; s]; zeckRepLen[n_] := Length[zeckRep[n]]; Table[zeckRepLen[n], {n, 0, 104}] (* Jean-François Alcover, Sep 27 2011 *)
    DigitCount[Select[Range[0, 1000], BitAnd[#, 2#] == 0 &], 2, 1] (* Jean-François Alcover, Jan 25 2018 *)
    Table[Length[DeleteCases[NestWhileList[# - Fibonacci[Floor[Log[Sqrt[5] * # + 3/2]/Log[GoldenRatio]]] &, n, # > 1 &], 0]], {n, 0, 143}] (* Alonso del Arte, May 14 2019 *)
    Flatten[Nest[{Flatten[#], #[[1]] + 1} &, {0, 1}, 9]] (* Paolo Xausa, Jun 17 2024 *)
  • PARI
    a(n,mx=0)=if(n<4,n>0,if(!mx,while(fibonacci(mx)n,mx--); 1+a(n-fibonacci(mx),mx-2)) \\ Charles R Greathouse IV, Feb 14 2013
    
  • PARI
    a(n)=if(n<4, n>0, my(k=2,s,t); while(fibonacci(k++)<=n,); while(k && n, t=fibonacci(k); if(t<=n, n-=t; s++); k--); s) \\ Charles R Greathouse IV, Sep 02 2015
    
  • Python
    from sympy import fibonacci
    def a(n):
        k=0
        x=0
        while n>0:
            k=0
            while fibonacci(k)<=n: k+=1
            x+=10**(k - 3)
            n-=fibonacci(k - 1)
        return str(x).count("1")
    print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 09 2017

Formula

a(n) = A000120(A003714(n)). - Reinhard Zumkeller, May 05 2005
a(n) = A107015(n) + A107016(n). - Reinhard Zumkeller, May 09 2005
a(n) = A143299(n+1) - 1. - Filip Zaludek, Oct 31 2016
a(n) = A007953(A014417(n)). - Amiram Eldar, Oct 10 2023

Extensions

Edited by N. J. A. Sloane Jun 27 2008 at the suggestion of R. J. Mathar and Don Reble

A105447 Positive integers whose representation as Roman Fibonacci numbers has exactly two symbols.

Original entry on oeis.org

4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 18, 19, 20, 22, 23, 24, 26, 29, 31, 32, 33, 35, 36, 37, 39, 42, 47, 50, 52, 53, 54, 56, 57, 58, 60, 63, 68, 76, 81, 84, 86, 87, 88, 90, 91, 92, 94, 97, 102, 110, 123, 131, 139, 141, 142, 143, 145, 146, 147, 149, 152, 157
Offset: 1

Views

Author

Jonathan Vos Post, Apr 09 2005

Keywords

Examples

			In Roman Fibonacci number representation:
4 = "22", 6 = "33", 7 = "52", 9 = "81", 10 = "55", 11 = "83", 12 = "1A",
14 = "A1", 15 = "A2", 16 = "88", 18 = "3B", 19 = "2B", 20 = "1B", ...
143 = "1F", 145 = "F1", 146 = "F2", 147 = "F3", 149 = "F5", 152 = "F8".
		

Crossrefs

Formula

a(n) is an element of A105447 iff A105446(n) = 2. a(n) is the sum or difference of two Fibonacci numbers A000045 and a(n) is not itself a Fibonacci number A000045.

A105448 Positive integers whose representation as Roman Fibonacci numbers has exactly three symbols.

Original entry on oeis.org

17, 25, 27, 28, 30, 38, 40, 41, 43, 44, 45, 46, 48, 49, 51, 59, 61, 62, 64, 65, 66, 67, 69, 70, 71, 72, 73, 74, 75, 77, 78, 79, 82, 83, 85, 93, 95, 96, 98, 99, 100, 101, 103, 104, 105, 107, 108, 109, 111, 112, 113, 115, 118, 124, 125, 126, 128, 132, 133, 134, 136, 140
Offset: 1

Views

Author

Jonathan Vos Post, Apr 09 2005

Keywords

Comments

A105446 gives the number of symbols in Roman Fibonacci numbers. A105447 gives positive integers whose representation as Roman Fibonacci numbers has exactly two symbols. A105449 gives positive integers whose representation as Roman Fibonacci numbers has exactly four symbols. A105450 gives positive integers whose representation as Roman Fibonacci numbers has exactly five symbols.

Examples

			In Roman Fibonacci number representation:
17 = "A22", 25 = "B22", 27 = "AA1", 28 = "AA2", 30 = "B81", 38 = "C22", 40 = "C33", 41 = "C52", 43 = "BB1", 44 = "BB2", 45 = "BB3", 46 = "1CA", 48 = "CA1", ..., 155 = "2FA", 156 = "1FA", 158 = "FA1", 159 = "FA2", 160 = "FA3".
		

Crossrefs

Formula

a(n) is an element of A105447 iff A105446(n) = 3.

A105449 Positive integers whose representation as Roman Fibonacci numbers has exactly four symbols.

Original entry on oeis.org

80, 106, 114, 116, 117, 119, 120, 121, 122, 127, 129, 130, 135, 137, 138
Offset: 1

Views

Author

Jonathan Vos Post, Apr 09 2005

Keywords

Comments

A105446 gives the number of symbols in Roman Fibonacci numbers. A105447 gives positive integers whose representation as Roman Fibonacci numbers has exactly two symbols. A105448 gives positive integers whose representation as Roman Fibonacci numbers has exactly three symbols. A105450 gives positive integers whose representation as Roman Fibonacci numbers has exactly five symbols.

Examples

			In Roman Fibonacci number representation:
80 = "DB22", 106 = "EA22", 114 = "DD22", 116 = "DD33", 117 = "DD52", 119 = "DD81", 120 = "DD55", 121 = "DD2A", 122 = "DD1A", 127 = "BF22", 129 = "BF33", 130 = "BF52", 135 = "AF22", 137 = "AF33", 138 = "AF52".
		

Crossrefs

Formula

a(n) is an element of A105449 iff A105446(n) = 4.

A296239 a(n) = distance from n to nearest Fibonacci number.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 16, 15, 14, 13, 12, 11, 10, 9
Offset: 0

Views

Author

Rémy Sigrist, Dec 09 2017

Keywords

Comments

The Fibonacci numbers correspond to sequence A000045.
This sequence is analogous to:
- A051699 (distance to nearest prime),
- A053188 (distance to nearest square),
- A053646 (distance to nearest power of 2),
- A053615 (distance to nearest oblong number),
- A053616 (distance to nearest triangular number),
- A061670 (distance to nearest power),
- A074989 (distance to nearest cube),
- A081134 (distance to nearest power of 3),
The local maxima of the sequence correspond to positive terms of A004695.
a(n) = 0 iff n = A000045(k) for some k >= 0.
a(n) = 1 iff n = A061489(k) for some k > 4.
For any n >= 0, abs(a(n+1) - a(n)) <= 1.
For any n > 0, a(n) < n, and a^k(n) = 0 for some k > 0 (where a^k denotes the k-th iterate of a); k equals A105446(n) for n = 1..80 (and possibly more values).
a(n) > max(a(n-1), a(n+1)) iff n = A001076(k) for some k > 1.

Examples

			For n = 42:
- A000045(9) = 34 <= 42 <= 55 = A000045(10),
- a(42) = min(42 - 34, 55 - 42) = min(8, 13) = 8.
		

Crossrefs

Programs

  • Mathematica
    fibPi[n_] := 1 + Floor[ Log[ GoldenRatio, 1 + n*Sqrt@5]]; f[n_] := Block[{m = fibPi@ n}, Min[n - Fibonacci[m -1], Fibonacci[m] - n]]; Array[f, 81, 0] (* Robert G. Wilson v, Dec 11 2017 *)
    With[{nn=80,fibs=Fibonacci[Range[0,20]]},Table[Abs[n-Nearest[fibs,n]][[1]],{n,0,nn}]] (* Harvey P. Dale, Jul 02 2022 *)
  • PARI
    a(n) = for (i=1, oo, if (n<=fibonacci(i), return (min(n-fibonacci(i-1), fibonacci(i)-n))))

Formula

a(n) = abs(n - Fibonacci(floor(log(sqrt(20)*n)/log((1 + sqrt(5))/2)-1))). - Jon E. Schoenfield, Dec 14 2017

A058978 Minimal number of (non-consecutive) Fibonacci numbers needed to get n by addition and subtraction.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 2, 3, 2, 2, 2, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 2, 2, 2, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 2, 3, 2, 2, 2, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 4, 3, 3, 3, 2
Offset: 1

Views

Author

Floor van Lamoen, Jan 15 2001

Keywords

Examples

			a(50) = 2 because 50 is not a Fibonacci number, but 50 = 55 - 5. - _Sean A. Irvine_, Sep 08 2022
		

Crossrefs

Extensions

a(50) corrected by Sean A. Irvine, Sep 08 2022

A358915 a(n) is the far-difference representation of n written in balanced ternary.

Original entry on oeis.org

0, 1, 3, 9, 26, 27, 78, 80, 81, 82, 234, 240, 242, 243, 244, 246, 702, 703, 720, 726, 728, 729, 730, 732, 738, 2105, 2106, 2107, 2109, 2160, 2161, 2178, 2184, 2186, 2187, 2188, 2190, 2196, 2213, 2214, 6315, 6317, 6318, 6319, 6321, 6327, 6479, 6480, 6481, 6483
Offset: 0

Views

Author

Peter Kagey, Dec 05 2022

Keywords

Comments

A far-difference representation of an integer is the unique way to write that integer of the sum/difference of Fibonacci numbers such that any two terms in the sum with the same sign differ by at least an index of 4 and any two terms with different signs differ by an index of at least 3.
This sequence is also the list of numbers whose balanced ternary representation has the property that all signed-digits with the same sign differ by at least 4 positions and all signed-digits with different signs differ by at least 3 positions.

Examples

			Let F_i be the i-th term of the 0-indexed Fibonacci sequence beginning 1, 2, 3, 5, 8, ... .
| n  | far-difference               | a(n)                  |
|----+------------+-----------------+-----------------+-----+
| 10 | 13 - 3     | F_5 - F_2       | 3^5 - 3^2       | 234 |
| 11 | 13 - 2     | F_5 - F_1       | 3^5 - 3^1       | 240 |
| 12 | 13 - 1     | F_5 - F_0       | 3^5 - 3^0       | 242 |
| 13 | 13         | F_5             | 3^5             | 243 |
| 14 | 13 + 1     | F_5 + F_0       | 3^5 + 3^0       | 244 |
| 15 | 13 + 2     | F_5 + F_1       | 3^5 + 3^1       | 246 |
| 16 | 21 - 5     | F_6 - F_3       | 3^6 - 3^3       | 702 |
| 17 | 21 - 5 + 1 | F_6 - F_3 + F_0 | 3^6 - 3^3 + 3^0 | 703 |
| 18 | 21 - 3     | F_6 - F_2       | 3^6 - 3^2       | 720 |
| 19 | 21 - 2     | F_6 - F_1       | 3^6 - 3^1       | 726 |
| 20 | 21 - 1     | F_6 - F_0       | 3^6 - 3^0       | 728 |
		

Crossrefs

Showing 1-7 of 7 results.