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-10 of 78 results. Next

A345101 Irregular triangle T(n, k) read by rows, n >= 0, k = 1..A000119(n); the n-th row contains the numbers m such that A022290(m) = n, in increasing order.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 8, 7, 9, 10, 11, 12, 16, 13, 17, 14, 18, 15, 19, 20, 21, 22, 24, 32, 23, 25, 33, 26, 34, 27, 28, 35, 36, 29, 37, 30, 38, 40, 31, 39, 41, 42, 43, 44, 48, 64, 45, 49, 65, 46, 50, 66, 47, 51, 52, 67, 68, 53, 69, 54, 56, 70, 72, 55, 57, 71, 73
Offset: 0

Views

Author

Rémy Sigrist, Jun 08 2021

Keywords

Comments

When interpreted as a flat sequence, yields a permutation of the nonnegative integers.

Examples

			Triangle begins:
     0    [0]
     1    [1]
     2    [2]
     3    [3, 4]
     4    [5]
     5    [6, 8]
     6    [7, 9]
     7    [10]
     8    [11, 12, 16]
     9    [13, 17]
    10    [14, 18]
    11    [15, 19, 20]
    12    [21]

Links

Crossrefs

Cf. A000119 (row lengths), A003714, A003754, A022290.

Programs

  • PARI
    See Links section.

Formula

T(n, 1) = A003754(n+1).
T(n, A000119(n)) = A003714(n).

A094608 Rectangular array T by antidiagonals: row n consists of ranks of n in A000119.

Original entry on oeis.org

1, 2, 4, 3, 6, 9, 5, 7, 12, 17, 8, 10, 14, 22, 25, 13, 11, 15, 27, 30, 38, 21, 16, 19, 28, 40, 43, 59, 34, 18, 20, 33, 41, 46, 67, 64, 55, 26, 23, 35, 48, 51, 77, 72, 98, 89, 29, 24, 36, 49, 61, 85, 80, 101, 106, 144, 42, 31, 44, 56, 62, 95, 93, 132, 114, 153, 233, 47, 32, 45
Offset: 1

Views

Author

Clark Kimberling, May 14 2004

Keywords

Comments

Every positive integer occurs exactly once in T; thus a is a permutation of the positive integers. Row 1 consists of Fibonacci numbers. To obtain T from the array T' in A094607, add 1 to every number in T', then shift row 1 one place to the right and fill the initial place with 1.

Examples

			A northwest corner of T:
1 2 3 5 8
4 6 7 10 11
9 12 14 15 19
17 22 27 28 33

Links

Crossrefs

Cf. A000045, A000119, A094607.

A002487 Stern's diatomic series (or Stern-Brocot sequence): a(0) = 0, a(1) = 1; for n > 0: a(2*n) = a(n), a(2*n+1) = a(n) + a(n+1).

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

Comments

Also called fusc(n) [Dijkstra].
a(n)/a(n+1) runs through all the reduced nonnegative rationals exactly once [Stern; Calkin and Wilf].
If the terms are written as an array:
column 0 1 2 3 4 5 6 7 8 9 ...
row 0: 0
row 1: 1
row 2: 1,2
row 3: 1,3,2,3
row 4: 1,4,3,5,2,5,3,4
row 5: 1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5
row 6: 1,6,5,9,4,11,7,10,3,11,8,13,5,12,7,9,2,9,7,12,5,13,8,11,3,10,...
...
then (ignoring row 0) the sum of the k-th row is 3^(k-1), each column is an arithmetic progression and the steps are nothing but the original sequence. - Takashi Tokita (butaneko(AT)fa2.so-net.ne.jp), Mar 08 2003
From N. J. A. Sloane, Oct 15 2017: (Start)
The above observation can be made more precise. Let A(n,k), n >= 0, 0 <= k <= 2^(n-1)-1 for k > 0, denote the entry in row n and column k of the left-justified array above.
The equations for columns 0,1,2,3,4,... are successively (ignoring row 0):
1 (n >= 1),
n (n >= 2),
n-1 (n >= 3),
2n-3 (n >= 3),
n-2 (n >= 4),
3n-7 (n >= 4),
...
and in general column k > 0 is given by
A(n,k) = a(k)*n - A156140(k) for n >= ceiling(log_2(k+1))+1, and 0 otherwise.
(End)
a(n) is the number of odd Stirling numbers S_2(n+1, 2r+1) [Carlitz].
Moshe Newman proved that the fraction a(n+1)/a(n+2) can be generated from the previous fraction a(n)/a(n+1) = x by 1/(2*floor(x) + 1 - x). The successor function f(x) = 1/(floor(x) + 1 - frac(x)) can also be used.
a(n+1) = number of alternating bit sets in n [Finch].
If f(x) = 1/(1 + floor(x) - frac(x)) then f(a(n-1)/a(n)) = a(n)/a(n+1) for n >= 1. If T(x) = -1/x and f(x) = y, then f(T(y)) = T(x) for x > 0. - Michael Somos, Sep 03 2006
a(n+1) is the number of ways of writing n as a sum of powers of 2, each power being used at most twice (the number of hyperbinary representations of n) [Carlitz; Lind].
a(n+1) is the number of partitions of the n-th integer expressible as the sum of distinct even-subscripted Fibonacci numbers (= A054204(n)), into sums of distinct Fibonacci numbers [Bicknell-Johnson, theorem 2.1].
a(n+1) is the number of odd binomial(n-k, k), 0 <= 2*k <= n. [Carlitz], corrected by Alessandro De Luca, Jun 11 2014
a(2^k) = 1. a(3*2^k) = a(2^(k+1) + 2^k) = 2. Sequences of terms between a(2^k) = 1 and a(2^(k+1)) = 1 are palindromes of length 2^k-1 with a(2^k + 2^(k-1)) = 2 in the middle. a(2^(k-1) + 1) = a(2^k - 1) = k+1 for k > 1. - Alexander Adamchuk, Oct 10 2006
The coefficients of the inverse of the g.f. of this sequence form A073469 and are related to binary partitions A000123. - Philippe Flajolet, Sep 06 2008
It appears that the terms of this sequence are the number of odd entries in the diagonals of Pascal's triangle at 45 degrees slope. - Javier Torres (adaycalledzero(AT)hotmail.com), Aug 06 2009
Let M be an infinite lower triangular matrix with (1, 1, 1, 0, 0, 0, ...) in every column shifted down twice:
1;
1, 0;
1, 1, 0;
0, 1, 0, 0;
0, 1, 1, 0, 0;
0, 0, 1, 0, 0, 0;
0, 0, 1, 1, 0, 0, 0;
...
Then this sequence A002487 (without initial 0) is the first column of lim_{n->oo} M^n. (Cf. A026741.) - Gary W. Adamson, Dec 11 2009 [Edited by M. F. Hasler, Feb 12 2017]
Member of the infinite family of sequences of the form a(n) = a(2*n); a(2*n+1) = r*a(n) + a(n+1), r = 1 for A002487 = row 1 in the array of A178239. - Gary W. Adamson, May 23 2010
Equals row 1 in an infinite array shown in A178568, sequences of the form
a(2*n) = r*a(n), a(2*n+1) = a(n) + a(n+1); r = 1. - Gary W. Adamson, May 29 2010
Row sums of A125184, the Stern polynomials. Equivalently, B(n,1), the n-th Stern polynomial evaluated at x = 1. - T. D. Noe, Feb 28 2011
The Kn1y and Kn2y triangle sums, see A180662 for their definitions, of A047999 lead to the sequence given above, e.g., Kn11(n) = A002487(n+1) - A000004(n), Kn12(n) = A002487(n+3) - A000012(n), Kn13(n) = A002487(n+5) - A000034(n+1) and Kn14(n) = A002487(n+7) - A157810(n+1). For the general case of the knight triangle sums see the Stern-Sierpiński triangle A191372. This triangle not only leads to Stern's diatomic series but also to snippets of this sequence and, quite surprisingly, their reverse. - Johannes W. Meijer, Jun 05 2011
Maximum of terms between a(2^k) = 1 and a(2^(k+1)) = 1 is the Fibonacci number F(k+2). - Leonid Bedratyuk, Jul 04 2012
Probably the number of different entries per antidiagonal of A223541. That would mean there are exactly a(n+1) numbers that can be expressed as a nim-product 2^x*2^y with x + y = n. - Tilman Piesk, Mar 27 2013
Let f(m,n) be the frequency of the integer n in the interval [a(2^(m-1)), a(2^m-1)]. Let phi(n) be Euler's totient function (A000010). Conjecture: for all integers m,n n<=m f(m,n) = phi(n). - Yosu Yurramendi, Sep 08 2014
Back in May 1995, it was proved that A000360 is the modulo 3 mapping, (+1,-1,+0)/2, of this sequence A002487 (without initial 0). - M. Jeremie Lafitte (Levitas), Apr 24 2017
Define a sequence chf(n) of Christoffel words over an alphabet {-,+}: chf(1) = '-'; chf(2*n+0) = negate(chf(n)); chf(2*n+1) = negate(concatenate(chf(n),chf(n+1))). Then the length of the chf(n) word is fusc(n) = a(n); the number of '-'-signs in the chf(n) word is c-fusc(n) = A287729(n); the number of '+'-signs in the chf(n) word is s-fusc(n) = A287730(n). See examples below. - I. V. Serov, Jun 01 2017
The sequence can be extended so that a(n) = a(-n), a(2*n) = a(n), a(2*n+1) = a(n) + a(n+1) for all n in Z. - Michael Somos, Jun 25 2019
Named after the German mathematician Moritz Abraham Stern (1807-1894), and sometimes also after the French clockmaker and amateur mathematician Achille Brocot (1817-1878). - Amiram Eldar, Jun 06 2021
It appears that a(n) is equal to the multiplicative inverse of A007305(n+1) mod A007306(n+1). For example, a(12) is 2, the multiplicative inverse of A007305(13) mod A007306(13), where A007305(13) is 4 and A007306(13) is 7. - Gary W. Adamson, Dec 18 2023

Examples

			Stern's diatomic array begins:
  1,1,
  1,2,1,
  1,3,2,3,1,
  1,4,3,5,2,5,3,4,1,
  1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5,1,
  1,6,5,9,4,11,7,10,3,11,8,13,5,12,7,9,2,9,7,12,5,13,8,11,3,10,7,11,4,9,...
  ...
a(91) = 19, because 91_10 = 1011011_2; b_6=b_4=b_3=b_1=b_0=1, b_5=b_2=0;  L=5; m_1=0, m_2=1, m_3=3, m_4=4, m_5=6; c_1=2, c_2=3, c_3=2, c_4=3; f(1)=1, f(2)=2, f(3)=5, f(4)=8, f(5)=19. - _Yosu Yurramendi_, Jul 13 2016
From _I. V. Serov_, Jun 01 2017: (Start)
a(n) is the length of the Christoffel word chf(n):
n  chf(n) A070939(n)   a(n)
1   '-'       1          1
2   '+'       2          1
3   '+-'      2          2
4   '-'       3          1
5   '--+'     3          3
6   '-+'      3          2
... (End)
G.f. = x + x^2 + 2*x^3 + x^4 + 3*x^5 + 2*x^6 + 3*x^7 + x^8 + ... - _Michael Somos_, Jun 25 2019

References

  • M. Aigner and G. M. Ziegler, Proofs from THE BOOK, 3rd ed., Berlin, Heidelberg, New York: Springer-Verlag, 2004, p. 97.
  • Elwyn R. Berlekamp, John H. Conway and Richard K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 114.
  • Krishna Dasaratha, Laure Flapan, Chansoo Lee, Cornelia Mihaila, Nicholas Neumann-Chun, Sarah Peluse and Matthew Stroegeny, A family of multi-dimensional continued fraction Stern sequences, Abtracts Amer. Math. Soc., Vol. 33 (#1, 2012), #1077-05-2543.
  • Edsger W. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232 (sequence is called fusc).
  • F. G. M. Eisenstein, Eine neue Gattung zahlentheoretischer Funktionen, welche von zwei Elementen abhaengen und durch gewisse lineare Funktional-Gleichungen definirt werden, Verhandlungen der Koenigl. Preuss. Akademie der Wiss. Berlin (1850), pp. 36-42, Feb 18, 1850. Werke, II, pp. 705-711.
  • Graham Everest, Alf van der Poorten, Igor Shparlinski and Thomas Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
  • Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.16.3; pp. 148-149.
  • Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 117.
  • Thomas Koshy, Fibonacci and Lucas numbers with applications, Wiley, 2001, p. 98.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A000120, A000123, A000360, A001045, A002083, A011655, A020950, A026741, A037227, A046815, A070871, A070872, A071883, A073459, A084091, A101624, A126606, A168081, A174980, A174981, A178239, A178568, A212288, A213369, A260443, A277020, A277325, A287729, A287730, A293160.
Record values are in A212289.
If the 1's are replaced by pairs of 1's we obtain A049456.
Inverse: A020946.
Cf. a(A001045(n)) = A000045(n). a(A062092(n)) = A000032(n+1).
Cf. A064881-A064886 (Stern-Brocot subtrees).
A column of A072170.
Cf. A049455 for the 0,1 version of Stern's diatomic array.
Cf. A000119, A262097 for analogous sequences in other bases and A277189, A277315, A277328 for related sequences with similar graphs.
Cf. A086592 and references therein to other sequences related to Kepler's tree of fractions.

Programs

  • Haskell
    a002487 n = a002487_list !! n
a002487_list = 0 : 1 : stern [1] where
   stern fuscs = fuscs' ++ stern fuscs' where
     fuscs' = interleave fuscs $ zipWith (+) fuscs $ (tail fuscs) ++ [1]
   interleave []     ys = ys
   interleave (x:xs) ys = x : interleave ys xs
-- Reinhard Zumkeller, Aug 23 2011
  • Julia
    using Nemo
function A002487List(len)
    a, A = QQ(0), [0,1]
    for n in 1:len
        a = next_calkin_wilf(a)
        push!(A, denominator(a))
    end
A end
A002487List(91) |> println # Peter Luschny, Mar 13 2018
  • Magma
    [&+[(Binomial(k, n-k-1) mod 2): k in [0..n]]: n in [0..100]]; // Vincenzo Librandi, Jun 18 2019
  • Maple
    A002487 := proc(n) option remember; if n <= 1 then n elif n mod 2 = 0 then procname(n/2); else procname((n-1)/2)+procname((n+1)/2); fi; end: seq(A002487(n),n=0..91);
A002487 := proc(m) local a,b,n; a := 1; b := 0; n := m; while n>0 do if type(n,odd) then b := a+b else a := a+b end if; n := floor(n/2); end do; b; end proc: seq(A002487(n),n=0..91); # Program adapted from E. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232. - Igor Urbiha (urbiha(AT)math.hr), Oct 28 2002. Since A007306(n) = a(2*n+1), this program can be adapted for A007306 by replacing b := 0 by b := 1.
A002487 := proc(n::integer) local k; option remember; if n = 0 then 0 elif n=1 then 1 else add(K(k,n-1-k)*procname(n - k), k = 1 .. n) end if end proc:
K := proc(n::integer, k::integer) local KC; if 0 <= k and k <= n and n-k <= 2 then KC:=1; else KC:= 0; end if; end proc: seq(A002487(n),n=0..91); # Thomas Wieder, Jan 13 2008
# next Maple program:
a:= proc(n) option remember; `if`(n<2, n,
      (q-> a(q)+(n-2*q)*a(n-q))(iquo(n, 2)))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Feb 11 2021
fusc := proc(n) local a, b, c; a := 1; b := 0;
    for c in convert(n, base, 2) do
        if c = 0 then a := a + b else b := a + b fi od;
    b end:
seq(fusc(n), n = 0..91); # Peter Luschny, Nov 09 2022
Stern := proc(n, u) local k, j, b;
    b := j -> nops({seq(Bits:-Xor(k, j-k), k = 0..j)}):
    ifelse(n=0, 1-u, seq(b(j), j = 2^(n-1)-1..2^n-1-u)) end:
seq(print([n], Stern(n, 1)), n = 0..5); # As shown in the comments.
seq(print([n], Stern(n, 0)), n = 0..5); # As shown in the examples. # Peter Luschny, Sep 29 2024
  • Mathematica
    a[0] = 0; a[1] = 1; a[n_] := If[ EvenQ[n], a[n/2], a[(n-1)/2] + a[(n+1)/2]]; Table[ a[n], {n, 0, 100}] (* end of program *)
Onemore[l_] := Transpose[{l, l + RotateLeft[l]}] // Flatten;
NestList[Onemore, {1}, 5] // Flatten  (*gives [a(1), ...]*) (* Takashi Tokita, Mar 09 2003 *)
ToBi[l_] := Table[2^(n - 1), {n, Length[l]}].Reverse[l]; Map[Length,
Split[Sort[Map[ToBi, Table[IntegerDigits[n - 1, 3], {n, 500}]]]]]  (*give [a(1), ...]*) (* Takashi Tokita, Mar 10 2003 *)
A002487[m_] := Module[{a = 1, b = 0, n = m}, While[n > 0, If[OddQ[n], b = a+b, a = a+b]; n = Floor[n/2]]; b]; Table[A002487[n], {n, 0, 100}] (* Jean-François Alcover, Sep 06 2013, translated from 2nd Maple program *)
a[0] = 0; a[1] = 1;
Flatten[Table[{a[2*n] = a[n], a[2*n + 1] = a[n] + a[n + 1]}, {n, 0, 50}]] (* Horst H. Manninger, Jun 09 2021 *)
nmax = 100; CoefficientList[Series[x*Product[(1 + x^(2^k) + x^(2^(k+1))), {k, 0, Floor[Log[2, nmax]] + 1}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Oct 08 2022 *)
  • PARI
    {a(n) = n=abs(n); if( n<2, n>0, a(n\2) + if( n%2, a(n\2 + 1)))};
  • PARI
    fusc(n)=local(a=1,b=0);while(n>0,if(bitand(n,1),b+=a,a+=b);n>>=1);b \\ Charles R Greathouse IV, Oct 05 2008
  • PARI
    A002487(n,a=1,b=0)=for(i=0,logint(n,2),if(bittest(n,i),b+=a,a+=b));b \\ M. F. Hasler, Feb 12 2017, updated Feb 14 2019
  • Python
    from functools import lru_cache
@lru_cache(maxsize=None)
def a(n): return n if n<2 else a(n//2) if n%2==0 else a((n - 1)//2) + a((n + 1)//2) # Indranil Ghosh, Jun 08 2017; corrected by Reza K Ghazi, Dec 27 2021
  • Python
    def a(n):
    a, b = 1, 0
    while n > 0:
        if n & 1:
            b += a
        else:
            a += b
        n >>= 1
    return b
# Reza K Ghazi, Dec 29 2021
  • Python
    def A002487(n): return sum(int(not (n-k-1) & ~k) for k in range(n)) # Chai Wah Wu, Jun 19 2022
  • Python
    # (fast way for big vectors)
from math import log, ceil
import numpy
how_many_terms = 2**20  # (Powers of 2 recommended but other integers are also possible.)
A002487, A002487[1]  = numpy.zeros(2**(ce:=ceil(log(how_many_terms,2))), dtype=object), 1
for exponent in range(1,ce):
    L, L2 = 2**exponent, 2**(exponent+1)
    A002487[L2 - 1] = exponent + 1
    A002487[L:L2][::2] = A002487[L >> 1: L]
    A002487[L + 1:L2 - 2][::2] = A002487[L:L2 - 3][::2]  +  A002487[L + 2:L2 - 1][::2]
print(list(A002487[0:100])) # Karl-Heinz Hofmann, Jul 22 2025
  • R
    N <- 50 # arbitrary
a <- 1
for (n in 1:N)
{
  a[2*n    ] = a[n]
  a[2*n + 1] = a[n] + a[n+1]
  a
}
a
# Yosu Yurramendi, Oct 04 2014
  • R
    # Given n, compute a(n) by taking into account the binary representation of n
a <- function(n){
  b <- as.numeric(intToBits(n))
  l <- sum(b)
  m <- which(b == 1)-1
  d <- 1
  if(l > 1) for(j in 1:(l-1)) d[j] <- m[j+1]-m[j]+1
  f <- c(0,1)
  if(l > 1) for(j in 3:(l+1)) f[j] <- d[j-2]*f[j-1]-f[j-2]
  return(f[l+1])
} # Yosu Yurramendi, Dec 13 2016
  • R
    # computes the sequence as a vector A, rather than function a() as above.
A <- c(1,1)
maxlevel <- 5 # by choice
for(m in 1:maxlevel) {
  A[2^(m+1)] <- 1
  for(k in 1:(2^m-1)) {
    r <- m - floor(log2(k)) - 1
    A[2^r*(2*k+1)] <- A[2^r*(2*k)] + A[2^r*(2*k+2)]
}}
A # Yosu Yurramendi, May 08 2018
  • Sage
    def A002487(n):
    M = [1, 0]
    for b in n.bits():
        M[b] = M[0] + M[1]
    return M[1]
print([A002487(n) for n in (0..91)])
# For a dual see A174980. Peter Luschny, Nov 28 2017
  • Scheme
    ;; An implementation of memoization-macro definec can be found for example in: http://oeis.org/wiki/Memoization
(definec (A002487 n) (cond ((<= n 1) n) ((even? n) (A002487 (/ n 2))) (else (+ (A002487 (/ (- n 1) 2)) (A002487 (/ (+ n 1) 2))))))
;; Antti Karttunen, Nov 05 2016

Formula

a(n+1) = (2*k+1)*a(n) - a(n-1) where k = floor(a(n-1)/a(n)). - David S. Newman, Mar 04 2001
Let e(n) = A007814(n) = exponent of highest power of 2 dividing n. Then a(n+1) = (2k+1)*a(n)-a(n-1), n > 0, where k = e(n). Moreover, floor(a(n-1)/a(n)) = e(n), in agreement with D. Newman's formula. - Dragutin Svrtan (dsvrtan(AT)math.hr) and Igor Urbiha (urbiha(AT)math.hr), Jan 10 2002
Calkin and Wilf showed 0.9588 <= limsup a(n)/n^(log(phi)/log(2)) <= 1.1709 where phi is the golden mean. Does this supremum limit = 1? - Benoit Cloitre, Jan 18 2004. Coons and Tyler show the limit is A246765 = 0.9588... - Kevin Ryde, Jan 09 2021
a(n) = Sum_{k=0..floor((n-1)/2)} (binomial(n-k-1, k) mod 2). - Paul Barry, Sep 13 2004
a(n) = Sum_{k=0..n-1} (binomial(k, n-k-1) mod 2). - Paul Barry, Mar 26 2005
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = v^3 + 2*u*v*w - u^2*w. - Michael Somos, May 02 2005
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^3), A(x^6)) where f(u1, u2, u3, u6) = u1^3*u6 - 3*u1^2*u2*u6 + 3*u2^3*u6 - u2^3*u3. - Michael Somos, May 02 2005
G.f.: x * Product_{k>=0} (1 + x^(2^k) + x^(2^(k+1))) [Carlitz].
a(n) = a(n-2) + a(n-1) - 2*(a(n-2) mod a(n-1)). - Mike Stay, Nov 06 2006
A079978(n) = (1 + e^(i*Pi*A002487(n)))/2, i=sqrt(-1). - Paul Barry, Jan 14 2005
a(n) = Sum_{k=1..n} K(k, n-k)*a(n - k), where K(n,k) = 1 if 0 <= k AND k <= n AND n-k <= 2 and K(n,k) = 0 else. (When using such a K-coefficient, several different arguments to K or several different definitions of K may lead to the same integer sequence. For example, if we drop the condition k <= n in the above definition, then we arrive at A002083 = Narayana-Zidek-Capell numbers.) - Thomas Wieder, Jan 13 2008
a(k+1)*a(2^n - k) - a(k)*a(2^n - (k+1)) = 1; a(2^n - k) + a(k) = a(2^(n+1) + k). Both formulas hold for 0 <= k <= 2^n - 1. G.f.: G(z) = a(1) + a(2)*z + a(3)*z^2 + ... + a(k+1)*z^k + ... Define f(z) = (1 + z + z^2), then G(z) = lim f(z)*f(z^2)*f(z^4)* ... *f(z^(2^n))*... = (1 + z + z^2)*G(z^2). - Arie Werksma (werksma(AT)tiscali.nl), Apr 11 2008
a(k+1)*a(2^n - k) - a(k)*a(2^n - (k+1)) = 1 (0 <= k <= 2^n - 1). - Arie Werksma (werksma(AT)tiscali.nl), Apr 18 2008
a(2^n + k) = a(2^n - k) + a(k) (0 <= k <= 2^n). - Arie Werksma (werksma(AT)tiscali.nl), Apr 18 2008
Let g(z) = a(1) + a(2)*z + a(3)*z^2 + ... + a(k+1)*z^k + ..., f(z) = 1 + z + z^2. Then g(z) = lim_{n->infinity} f(z)*f(z^2)*f(z^4)*...*f(z^(2^n)), g(z) = f(z)*g(z^2). - Arie Werksma (werksma(AT)tiscali.nl), Apr 18 2008
For 0 <= k <= 2^n - 1, write k = b(0) + 2*b(1) + 4*b(2) + ... + 2^(n-1)*b(n-1) where b(0), b(1), etc. are 0 or 1. Define a 2 X 2 matrix X(m) with entries x(1,1) = x(2,2) = 1, x(1,2) = 1 - b(m), x(2,1) = b(m). Let P(n)= X(0)*X(1)* ... *X(n-1). The entries of the matrix P are members of the sequence: p(1,1) = a(k+1), p(1,2) = a(2^n - (k+1)), p(2,1) = a(k), p(2,2) = a(2^n - k). - Arie Werksma (werksma(AT)tiscali.nl), Apr 20 2008
Let f(x) = A030101(x); if 2^n + 1 <= x <= 2^(n + 1) and y = 2^(n + 1) - f(x - 1) then a(x) = a(y). - Arie Werksma (Werksma(AT)Tiscali.nl), Jul 11 2008
a(n) = A126606(n + 1) / 2. - Reikku Kulon, Oct 05 2008
Equals infinite convolution product of [1,1,1,0,0,0,0,0,0] aerated A000079 - 1 times, i.e., [1,1,1,0,0,0,0,0,0] * [1,0,1,0,1,0,0,0,0] * [1,0,0,0,1,0,0,0,1]. - Mats Granvik and Gary W. Adamson, Oct 02 2009; corrected by Mats Granvik, Oct 10 2009
a(2^(p+2)*n+2^(p+1)-1) - a(2^(p+1)*n+2^p-1) = A007306(n+1), p >= 0 and n >= 0. - Johannes W. Meijer, Feb 07 2013
a(2*n-1) = A007306(n), n > 0. - Yosu Yurramendi, Jun 23 2014
a(n*2^m) = a(n), m>0, n > 0. - Yosu Yurramendi, Jul 03 2014
a(k+1)*a(2^m+k) - a(k)*a(2^m+(k+1)) = 1 for m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Nov 07 2014
a(2^(m+1)+(k+1))*a(2^m+k) - a(2^(m+1)+k)*a(2^m+(k+1)) = 1 for m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Nov 07 2014
a(5*2^k) = 3. a(7*2^k) = 3. a(9*2^k) = 4. a(11*2^k) = 5. a(13*2^k) = 5. a(15*2^k) = 4. In general: a((2j-1)*2^k) = A007306(j), j > 0, k >= 0 (see Adamchuk's comment). - Yosu Yurramendi, Mar 05 2016
a(2^m+2^m'+k') = a(2^m'+k')*(m-m'+1) - a(k'), m >= 0, m' <= m-1, 0 <= k' < 2^m'. - Yosu Yurramendi, Jul 13 2016
From Yosu Yurramendi, Jul 13 2016: (Start)
Let n be a natural number and [b_m b_(m-1) ... b_1 b_0] its binary expansion with b_m=1.
Let L = Sum_{i=0..m} b_i be the number of binary digits equal to 1 (L >= 1).
Let {m_j: j=1..L} be the set of subindices such that b_m_j = 1, j=1..L, and 0 <= m_1 <= m_2 <= ... <= m_L = m.
If L = 1 then c_1 = 1, otherwise let {c_j: j=1..(L-1)} be the set of coefficients such that c_(j) = m_(j+1) - m_j + 1, 1 <= j <= L-1.
Let f be a function defined on {1..L+1} such that f(1) = 0, f(2) = 1, f(j) = c_(j-2)*f(j-1) - f(j-2), 3 <= j <= L+1.
Then a(n) = f(L+1) (see example). (End)
a(n) = A001222(A260443(n)) = A000120(A277020(n)). Also a(n) = A000120(A101624(n-1)) for n >= 1. - Antti Karttunen, Nov 05 2016
(a(n-1) + a(n+1))/a(n) = A037227(n) for n >= 1. - Peter Bala, Feb 07 2017
a(0) = 0; a(3n) = 2*A000360(3n-1); a(3n+1) = 2*A000360(3n) - 1; a(3n+2) = 2*A000360(3n+1) + 1. - M. Jeremie Lafitte (Levitas), Apr 24 2017
From I. V. Serov, Jun 14 2017: (Start)
a(n) = A287896(n-1) - 1*A288002(n-1) for n > 1;
a(n) = A007306(n-1) - 2*A288002(n-1) for n > 1. (End)
From Yosu Yurramendi, Feb 14 2018: (Start)
a(2^(m+2) + 2^(m+1) + k) - a(2^(m+1) + 2^m + k) = 2*a(k), m >= 0, 0 <= k < 2^m.
a(2^(m+2) + 2^(m+1) + k) - a(2^(m+1) + k) = a(2^m + k), m >= 0, 0 <= k < 2^m.
a(2^m + k) = a(k)*(m - floor(log_2(k)) - 1) + a(2^(floor(log_2(k))+1) + k), m >= 0, 0 < k < 2^m, a(2^m) = 1, a(0) = 0. (End)
From Yosu Yurramendi, May 08 2018: (Start)
a(2^m) = 1, m >= 0.
a(2^r*(2*k+1)) = a(2^r*(2*k)) + a(2^r*(2*k+2)), r < - m - floor(log_2(k)) - 1, m > 0, 1 <= k < 2^m. (End)
Trow(n) = [card({k XOR (j-k): k=0..j}) for j = 2^(n-1)-1..2^n-2] when regarded as an irregular table (n >= 1). - Peter Luschny, Sep 29 2024
a(n) = A000120(A168081(n)). - Karl-Heinz Hofmann, Jun 16 2025

Extensions

Additional references and comments from Len Smiley, Joshua Zucker, Rick L. Shepherd and Herbert S. Wilf
Typo in definition corrected by Reinhard Zumkeller, Aug 23 2011
Incorrect formula deleted and text edited by Johannes W. Meijer, Feb 07 2013

A000071 a(n) = Fibonacci(n) - 1.

Original entry on oeis.org

0, 0, 1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583, 4180, 6764, 10945, 17710, 28656, 46367, 75024, 121392, 196417, 317810, 514228, 832039, 1346268, 2178308, 3524577, 5702886, 9227464, 14930351, 24157816, 39088168, 63245985, 102334154
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) is the number of allowable transition rules for passing from one change to the next (on n-1 bells) in the English art of bell-ringing. This is also the number of involutions in the symmetric group S_{n-1} which can be represented as a product of transpositions of consecutive numbers from {1, 2, ..., n-1}. Thus for n = 6 we have a(6) from (12), (12)(34), (12)(45), (23), (23)(45), (34), (45), for instance. See my 1983 Math. Proc. Camb. Phil. Soc. paper. - Arthur T. White, letter to N. J. A. Sloane, Dec 18 1986
Number of permutations p of {1, 2, ..., n-1} such that max|p(i) - i| = 1. Example: a(4) = 2 since only the permutations 132 and 213 of {1, 2, 3} satisfy the given condition. - Emeric Deutsch, Jun 04 2003 [For a(5) = 4 we have 2143, 1324, 2134 and 1243. - Jon Perry, Sep 14 2013]
Number of 001-avoiding binary words of length n-3. a(n) is the number of partitions of {1, ..., n-1} into two blocks in which only 1- or 2-strings of consecutive integers can appear in a block and there is at least one 2-string. E.g., a(6) = 7 because the enumerated partitions of {1, 2, 3, 4, 5} are 124/35, 134/25, 14/235, 13/245, 1245/3, 145/23, 125/34. - Augustine O. Munagi, Apr 11 2005
Numbers for which only one Fibonacci bit-representation is possible and for which the maximal and minimal Fibonacci bit-representations (A104326 and A014417) are equal. For example, a(12) = 10101 because 8 + 3 + 1 = 12. - Casey Mongoven, Mar 19 2006
Beginning with a(2), the "Recamán transform" (see A005132) of the Fibonacci numbers (A000045). - Nick Hobson, Mar 01 2007
Starting with nonzero terms, a(n) gives the row sums of triangle A158950. - Gary W. Adamson, Mar 31 2009
a(n+2) is the minimum number of elements in an AVL tree of height n. - Lennert Buytenhek (buytenh(AT)wantstofly.org), May 31 2010
a(n) is the number of branch nodes in the Fibonacci tree of order n-1. A Fibonacci tree of order n (n >= 2) is a complete binary tree whose left subtree is the Fibonacci tree of order n-1 and whose right subtree is the Fibonacci tree of order n-2; each of the Fibonacci trees of order 0 and 1 is defined as a single node (see the Knuth reference, p. 417). - Emeric Deutsch, Jun 14 2010
a(n+3) is the number of distinct three-strand positive braids of length n (cf. Burckel). - Maxime Bourrigan, Apr 04 2011
a(n+1) is the number of compositions of n with maximal part 2. - Joerg Arndt, May 21 2013
a(n+2) is the number of leafs of great-grandparent DAG (directed acyclic graph) of height n. A great-grandparent DAG of height n is a single node for n = 1; for n > 1 each leaf of ggpDAG(n-1) has two child nodes where pairs of adjacent new nodes are merged into single node if and only if they have disjoint grandparents and same great-grandparent. Consequence: a(n) = 2*a(n-1) - a(n-3). - Hermann Stamm-Wilbrandt, Jul 06 2014
2 and 7 are the only prime numbers in this sequence. - Emmanuel Vantieghem, Oct 01 2014
From Russell Jay Hendel, Mar 15 2015: (Start)
We can establish Gerald McGarvey's conjecture mentioned in the Formula section, however we require n > 4. We need the following 4 prerequisites.
(1) a(n) = F(n) - 1, with {F(n)}A000045.%20(2)%20(Binet%20form)%20F(n)%20=%20(d%5En%20-%20e%5En)/sqrt(5)%20with%20d%20=%20phi%20and%20e%20=%201%20-%20phi,%20de%20=%20-1%20and%20d%20+%20e%20=%201.%20It%20follows%20that%20a(n)%20=%20(d(n)%20-%20e(n))/sqrt(5)%20-%201.%20(3)%20To%20prove%20floor(x)%20=%20y%20is%20equivalent%20to%20proving%20that%20x%20-%20y%20lies%20in%20the%20half-open%20interval%20%5B0,%201).%20(4)%20The%20series%20%7Bs(n)%20=%20c1%20x%5En%20+%20c2%7D">{n >= 1} the Fibonacci numbers A000045. (2) (Binet form) F(n) = (d^n - e^n)/sqrt(5) with d = phi and e = 1 - phi, de = -1 and d + e = 1. It follows that a(n) = (d(n) - e(n))/sqrt(5) - 1. (3) To prove floor(x) = y is equivalent to proving that x - y lies in the half-open interval [0, 1). (4) The series {s(n) = c1 x^n + c2}{n >= 1}, with -1 < x < 0, and c1 and c2 positive constants, converges by oscillation with s(1) < s(3) < s(5) < ... < s(6) < s(4) < s(2). If follows that for any odd n, the open interval (s(n), s(n+1)) contains the subsequence {s(t)}_{t >= n + 2}. Using these prerequisites we can analyze the conjecture.
Using prerequisites (2) and (3) we see we must prove, for all n > 4, that d((d^(n-1) - e^(n-1))/sqrt(5) - 1) - (d^n - e^n)/sqrt(5) + 1 + c lies in the interval [0, 1). But de = -1, implying de^(n-1) = -e^(n-2). It follows that we must equivalently prove (for all n > 4) that E(n, c) = (e^(n-2) + e^n)/sqrt(5) + 1 - d + c = e^(n-2) (e^2 + 1)/sqrt(5) + e + c lies in [0, 1). Clearly, for any particular n, E(n, c) has extrema (maxima, minima) when c = 2*(1-d) and c = (1+d)*(1-d). Therefore, the proof is completed by using prerequisite (4). It suffices to verify E(5, 2*(1-d)) = 0, E(6, 2*(1-d)) = 0.236068, E(5, (1-d)*(1+d)) = 0.618034, E(6, (1-d)*(1+d)) = 0.854102, all lie in [0, 1).
(End)
a(n) can be shown to be the number of distinct nonempty matchings on a path with n vertices. (A matching is a collection of disjoint edges.) - Andrew Penland, Feb 14 2017
Also, for n > 3, the lexicographically earliest sequence of positive integers such that {phi*a(n)} is located strictly between {phi*a(n-1)} and {phi*a(n-2)}. - Ivan Neretin, Mar 23 2017
From Eric M. Schmidt, Jul 17 2017: (Start)
Number of sequences (e(1), ..., e(n-2)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) <= e(k). [Martinez and Savage, 2.5]
Number of sequences (e(1), ..., e(n-2)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(j) <= e(k) and e(i) != e(k). [Martinez and Savage, 2.5]
(End)
Numbers whose Zeckendorf (A014417) and dual Zeckendorf (A104326) representations are the same: alternating digits of 1 and 0. - Amiram Eldar, Nov 01 2019
a(n+2) is the length of the longest array whose local maximum element can be found in at most n reveals. See link to the puzzle by Alexander S. Kulikov. - Dmitry Kamenetsky, Aug 08 2020
a(n+2) is the number of nonempty subsets of {1,2,...,n} that contain no consecutive elements. For example, the a(6)=7 subsets of {1,2,3,4} are {1}, {2}, {3}, {4}, {1,3}, {1,4} and {2,4}. - Muge Olucoglu, Mar 21 2021
a(n+3) is the number of allowed patterns of length n in the even shift (that is, a(n+3) is the number of binary words of length n in which there are an even number of 0s between any two occurrences of 1). For example, a(7)=12 and the 12 allowed patterns of length 4 in the even shift are 0000, 0001, 0010, 0011, 0100, 0110, 0111, 1000, 1001, 1100, 1110, 1111. - Zoran Sunic, Apr 06 2022
Conjecture: for k a positive odd integer, the sequence {a(k^n): n >= 1} is a strong divisibility sequence; that is, for n, m >= 1, gcd(a(k^n), a(k^m)) = a(k^gcd(n,m)). - Peter Bala, Dec 05 2022
In general, the sum of a second-order linear recurrence having signature (c,d) will be a third-order recurrence having a signature (c+1,d-c,-d). - Gary Detlefs, Jan 05 2023
a(n) is the number of binary strings of length n-2 whose longest run of 1's is of length 1, for n >= 3. - Félix Balado, Apr 03 2025

References

  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 1.
  • GCHQ, The GCHQ Puzzle Book, Penguin, 2016. See page 28.
  • M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 64.
  • D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 155.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29.

Links

Crossrefs

Cf. A000032, A000045, A000119, A001611, A001654, A001911, A005968, A005969.
Cf. A006327, A014417, A054761, A081006, A081007, A081008, A081009, A083368.
Cf. A098531, A098532, A098533, A101220, A104326, A105488, A105489, A119282.
Cf. A128697, A157725, A157726, A157727, A157728, A157729, A158950, A167616.
Cf. A001622, A228074.
Antidiagonal sums of array A004070.
Right-hand column 2 of triangle A011794.
Related to sum of Fibonacci(kn) over n. Cf. A099919, A058038, A138134, A053606.
Subsequence of A226538. Also a subsequence of A061489.

Programs

  • Haskell
    a000071 n = a000071_list !! n
a000071_list = map (subtract 1) $ tail a000045_list
-- Reinhard Zumkeller, May 23 2013
  • Magma
    [Fibonacci(n)-1: n in [1..60]]; // Vincenzo Librandi, Apr 04 2011
  • Maple
    A000071 := proc(n) combinat[fibonacci](n)-1 ; end proc; # R. J. Mathar, Apr 07 2011
a:= n-> (Matrix([[1, 1, 0], [1, 0, 0], [1, 0, 1]])^(n-1))[3, 2]; seq(a(n), n=1..50); # Alois P. Heinz, Jul 24 2008
  • Mathematica
    Fibonacci[Range[40]] - 1 (* or *) LinearRecurrence[{2, 0, -1}, {0, 0, 1}, 40] (* Harvey P. Dale, Aug 23 2013 *)
Join[{0}, Accumulate[Fibonacci[Range[0, 39]]]] (* Alonso del Arte, Oct 22 2017, based on Giorgi Dalakishvili's formula *)
  • PARI
    {a(n) = if( n<1, 0, fibonacci(n)-1)};
  • SageMath
    [fibonacci(n)-1 for n in range(1,60)] # G. C. Greubel, Oct 21 2024

Formula

a(n) = A000045(n) - 1.
a(0) = -1, a(1) = 0; thereafter a(n) = a(n-1) + a(n-2) + 1.
a(n) = A101220(1, 1, n-2), for n > 1.
G.f.: x^3/((1-x-x^2)*(1-x)). - Simon Plouffe in his 1992 dissertation, dropping initial 0's
a(n) = 2*a(n-1) - a(n-3). - R. H. Hardin, Apr 02 2011
Partial sums of Fibonacci numbers. - Wolfdieter Lang
a(n) = -1 + (A*B^n + C*D^n)/10, with A, C = 5 +- 3*sqrt(5), B, D = (1 +- sqrt(5))/2. - Ralf Stephan, Mar 02 2003
a(1) = 0, a(2) = 0, a(3) = 1, then a(n) = ceiling(phi*a(n-1)) where phi is the golden ratio (1 + sqrt(5))/2. - Benoit Cloitre, May 06 2003
Conjecture: for all c such that 2*(2 - Phi) <= c < (2 + Phi)*(2 - Phi) we have a(n) = floor(Phi*a(n-1) + c) for n > 4. - Gerald McGarvey, Jul 22 2004. This is true provided n > 3 is changed to n > 4, see proof in Comments section. - Russell Jay Hendel, Mar 15 2015
a(n) = Sum_{k = 0..floor((n-2)/2)} binomial(n-k-2, k+1). - Paul Barry, Sep 23 2004
a(n+3) = Sum_{k = 0..floor(n/3)} binomial(n-2*k, k)*(-1)^k*2^(n-3*k). - Paul Barry, Oct 20 2004
a(n+1) = Sum(binomial(n-r, r)), r = 1, 2, ... which is the case t = 2 and k = 2 in the general case of t-strings and k blocks: a(n+1, k, t) = Sum(binomial(n-r*(t-1), r)*S2(n-r*(t-1)-1, k-1)), r = 1, 2, ... - Augustine O. Munagi, Apr 11 2005
a(n) = Sum_{k = 0..n-2} k*Fibonacci(n - k - 3). - Ross La Haye, May 31 2006
a(n) = term (3, 2) in the 3 X 3 matrix [1, 1, 0; 1, 0, 0; 1, 0, 1]^(n-1). - Alois P. Heinz, Jul 24 2008
For n >= 4, a(n) = ceiling(phi*a(n-1)), where phi is the golden ratio. - Vladimir Shevelev, Jul 04 2010
Closed-form without two leading zeros g.f.: 1/(1 - 2*x - x^3); ((5 + 2*sqrt(5))*((1 + sqrt(5))/2)^n + (5 - 2*sqrt(5))*((1 - sqrt(5))/2)^n - 5)/5; closed-form with two leading 0's g.f.: x^2/(1 - 2*x - x^3); ((5 + sqrt(5))*((1 + sqrt(5))/2)^n + (5 - sqrt(5))*((1 - sqrt(5))/2)^n - 10)/10. - Tim Monahan, Jul 10 2011
A000119(a(n)) = 1. - Reinhard Zumkeller, Dec 28 2012
a(n) = A228074(n - 1, 2) for n > 2. - Reinhard Zumkeller, Aug 15 2013
G.f.: Q(0)*x^2/2, where Q(k) = 1 + 1/(1 - x*(4*k + 2 - x^2)/( x*(4*k + 4 - x^2) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 30 2013
A083368(a(n+3)) = n. - Reinhard Zumkeller, Aug 10 2014
E.g.f.: 1 - exp(x) + 2*exp(x/2)*sinh(sqrt(5)*x/2)/sqrt(5). - Ilya Gutkovskiy, Jun 15 2016
a(n) = A000032(3+n) - 1 mod A000045(3+n). - Mario C. Enriquez, Apr 01 2017
a(n) = Sum_{i=0..n-2} Fibonacci(i). - Giorgi Dalakishvili (mcnamara_gio(AT)yahoo.com), Apr 02 2005 [corrected by Doug Bell, Jun 01 2017]
a(n+2) = Sum_{j = 0..floor(n/2)} Sum_{k = 0..j} binomial(n - 2*j, k+1)*binomial(j, k). - Tony Foster III, Sep 08 2017
From Peter Bala, Nov 12 2021: (Start)
a(4*n) = Fibonacci(2*n+1)*Lucas(2*n-1) = A081006(n);
a(4*n+1) = Fibonacci(2*n)*Lucas(2*n+1) = A081007(n);
a(4*n+2) = Fibonacci(2*n)*Lucas(2*n+2) = A081008(n);
a(4*n+3) = Fibonacci(2*n+2)*Lucas(2*n+1) = A081009(n). (End)
G.f.: x^3/((1 - x - x^2)*(1 - x)) = Sum_{n >= 0} (-1)^n * x^(n+3) *( Product_{k = 1..n} (k - x)/Product_{k = 1..n+2} (1 - k*x) ) (a telescoping series). - Peter Bala, May 08 2024
Product_{n>=4} (1 + (-1)^n/a(n)) = 3*phi/4, where phi is the golden ratio (A001622). - Amiram Eldar, Nov 28 2024

Extensions

Edited by N. J. A. Sloane, Apr 04 2011

A000121 Number of representations of n as a sum of Fibonacci numbers (1 is allowed twice as a part).

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of partitions into distinct Fibonacci parts (1 counted as two distinct Fibonacci numbers).
Inverse Euler transform of sequence has generating function sum_{n>0} x^F(n)-x^{2F(n)} where F() is Fibonacci.

References

  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A000119, A274262, A356874.
Least inverse is A083853.

Programs

  • Maple
    with(combinat): p := product((1+x^fibonacci(i)), i=1..25): s := series(p,x,1000): for k from 0 to 250 do printf(`%d,`,coeff(s,x,k)) od:
  • Mathematica
    imax = 20; p = Product[1+x^Fibonacci[i], {i, 1, imax}]; CoefficientList[p, x][[1 ;; Fibonacci[imax]+1]] (* Jean-François Alcover, Feb 04 2016, adapted from Maple *)
nmax = 91; s=Total/@Subsets[Select[Table[Fibonacci[i], {i, nmax}], # <= nmax &]];
Table[Count[s, n], {n, 0, nmax}] (* Robert Price, Aug 17 2020 *)
  • PARI
    a(n)=local(A,m,f); if(n<0,0,A=1+x*O(x^n); m=1; while((f=fibonacci(m))<=n,A*=1+x^f; m++); polcoeff(A,n))

Formula

a(0) = 1; for n >= 1, a(n) = A000119(n) + A000119(n-1). - Peter Munn, Jan 19 2018

Extensions

More terms from James Sellers, Jun 18 2000

A003107 Number of partitions of n into Fibonacci parts (with a single type of 1).

Original entry on oeis.org

1, 1, 2, 3, 4, 6, 8, 10, 14, 17, 22, 27, 33, 41, 49, 59, 71, 83, 99, 115, 134, 157, 180, 208, 239, 272, 312, 353, 400, 453, 509, 573, 642, 717, 803, 892, 993, 1102, 1219, 1350, 1489, 1640, 1808, 1983, 2178, 2386, 2609, 2854, 3113, 3393, 3697, 4017, 4367, 4737
Offset: 0

Views

Author

N. J. A. Sloane, Herman P. Robinson

Keywords

Comments

The partitions allow repeated items but the order of items is immaterial (1+2=2+1). - Ron Knott, Oct 22 2003
A098641(n) = a(A000045(n)). - Reinhard Zumkeller, Apr 24 2005

Examples

			a(4) = 4 since the 4 partitions of 4 using only Fibonacci numbers, repetitions allowed, are 1+1+1+1, 2+2, 2+1+1, 3+1.

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A007000, A005092, A028290 (where the only Fibonacci numbers allowed are 1, 2, 3, 5 and 8).
Cf. A000045, A000119, A102848, A238998.
Row sums of A319394.

Programs

  • Haskell
    import Data.MemoCombinators (memo2, integral)
a003107 n = a003107_list !! n
a003107_list = map (p' 2) [0..] where
   p' = memo2 integral integral p
   p _ 0 = 1
   p k m | m < fib   = 0
         | otherwise = p' k (m - fib) + p' (k + 1) m where fib = a000045 k
-- Reinhard Zumkeller, Dec 09 2015
  • Maple
    F:= combinat[fibonacci]:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<2, 0,
       b(n, i-1)+`if`(F(i)>n, 0, b(n-F(i), i))))
    end:
a:= proc(n) local j; for j from ilog[(1+sqrt(5))/2](n+1)
       while F(j+1)<=n do od; b(n, j)
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Jul 11 2013
  • Mathematica
    CoefficientList[ Series[1/ Product[1 - x^Fibonacci[i], {i, 2, 21}], {x, 0, 53}], x] (* Robert G. Wilson v, Mar 28 2006 *)
nmax = 53;
s = Table[Fibonacci[n], {n, nmax}];
Table[Count[IntegerPartitions@n, x_ /; SubsetQ[s, x]], {n, 0, nmax}] (* Robert Price, Jul 31 2020 *)
F = Fibonacci;
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 2, 0,
     b[n, i - 1] + If[F[i] > n, 0, b[n - F[i], i]]]];
a[n_] := Module[{j}, For[j = Floor@Log[(1+Sqrt[5])/2, n+1],
     F[j + 1] <= n, j++]; b[n, j]];
a /@ Range[0, 100] (* Jean-François Alcover, May 21 2021, after Alois P. Heinz *)
  • PARI
    f(x,y,z)=if(xCharles R Greathouse IV, Dec 14 2015

Formula

a(n) = (1/n)*Sum_{k=1..n} A005092(k)*a(n-k), n > 1, a(0)=1. - Vladeta Jovovic, Jan 21 2002
G.f.: Product_{i>=2} 1/(1-x^fibonacci(i)). - Ron Knott, Oct 22 2003
a(n) = f(n,1,1) with f(x,y,z) = if xReinhard Zumkeller, Nov 11 2009
G.f.: 1 + Sum_{i>=2} x^Fibonacci(i) / Product_{j=2..i} (1 - x^Fibonacci(j)). - Ilya Gutkovskiy, May 07 2017

Extensions

More terms from Vladeta Jovovic, Jan 21 2002

A067595 Number of partitions of n into distinct Lucas parts (A000032).

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 2, 3, 2, 2, 3, 3, 3, 3, 4, 3, 3, 3, 4, 3, 3, 5, 4, 4, 4, 5, 3, 3, 4, 4, 4, 4, 6, 5, 5, 5, 6, 4, 4, 6, 5, 5, 5, 6, 4, 4, 4, 5, 4, 4, 7, 6, 6, 6, 8, 5, 5, 7, 6, 6, 6, 8, 6, 6, 6, 7, 5, 5, 8, 6, 6, 6, 7, 4, 4, 5, 5, 5, 5, 8, 7, 7, 7, 9, 6, 6, 9, 8, 8, 8, 10, 7, 7, 7, 8, 6, 6, 10, 8, 8, 8, 10, 6, 6, 8
Offset: 0

Views

Author

Naohiro Nomoto, Jan 31 2002

Keywords

Links

Crossrefs

Cf. A000032, A000119.

Programs

  • Mathematica
    n1 = 10; n2 = LucasL[n1]; (1 + x^2)*Product[1 + x^LucasL[n], {n, 1, n1}] + O[x]^n2 // CoefficientList[#, x]& (* Jean-François Alcover, Feb 17 2017, after Joerg Arndt *)
  • PARI
    L(n) = fibonacci(n+1) + fibonacci(n-1);
N = 66;  x = 'x + O('x^N);
gf = prod(n=0, 11, 1 + x^L(n) );
\\gf = prod(n=1, 11, 1 + x^L(n) ) * (1+x^2); \\ same g.f.
Vec(gf) \\ Joerg Arndt, Jul 14 2013

Formula

G.f.: B(x) * (1 + x^2) where B(x) is the g.f. of A003263. [Joerg Arndt, Jul 14 2013]

Extensions

Corrected a(0), Joerg Arndt, Jul 14 2013

A065033 1 appears three times, other numbers twice.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30, 30, 31, 31, 32, 32, 33, 33, 34, 34, 35
Offset: 0

Views

Author

N. J. A. Sloane, Nov 04 2001

Keywords

Comments

Gives the number of terms in n-th row of many common tables.
Number of partitions of the (n+1)-th Fibonacci number into distinct Fibonacci numbers: a(n) = A000119(A000045(n)), see also A098641. - Reinhard Zumkeller, Apr 24 2005
a(n) = length of run n+1 of consecutive 4s in A254338. - Reinhard Zumkeller, Feb 27 2015
This is the Engel expansion of A070910 + A096789. - Benedict W. J. Irwin, Dec 16 2016

Links

Crossrefs

Cf. A004526, A008619.
Cf. A254338.

Programs

Formula

From Philippe Deléham, Sep 28 2006: (Start)
a(n) = a(n-1)+a(n-2)-a(n-3) for n>3.
G.f.: (1-x^2+x^3)/(1-x-x^2+x^3). (End)
a(n) = floor((n+1)/2) + 0^n. - Reinhard Zumkeller, Feb 27 2015
E.g.f.: (2 + exp(x)*x + sinh(x))/2. - Stefano Spezia, Aug 05 2025

A103344 Number of representations of n as a sum of distinct elements of the Fibonacci-type sequence beginning 1, 4, 5, 9, 14, 23, 37, 60, ....

Original entry on oeis.org

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

Views

Author

Casey Mongoven, Feb 01 2005

Keywords

Links

Crossrefs

Cf. A000121, A000119, A067595, A003263, A103343.

Programs

  • Mathematica
    imax = 10;
f[1] = 1; f[2] = 4; f[n_] := f[n] = f[n-1] + f[n-2];
p = Product[1+x^f[i], {i, 1, imax}];
CoefficientList[p, x][[1;;f[imax]+1]] (* Jean-François Alcover, May 08 2019 *)

Extensions

a(0)=1 corrected by Alois P. Heinz, Sep 16 2015

A120562 Sum of binomial coefficients binomial(i+j, i) modulo 2 over all pairs (i,j) of positive integers satisfying 3i+j=n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 2, 3, 1, 3, 2, 3, 2, 4, 3, 5, 1, 4, 3, 4, 2, 5, 3, 5, 2, 5, 4, 6, 3, 7, 5, 8, 1, 6, 4, 5, 3, 7, 4, 7, 2, 6, 5, 7, 3, 8, 5, 8, 2, 7, 5, 7, 4, 9, 6, 10, 3, 9, 7, 10, 5, 12, 8, 13, 1
Offset: 0

Views

Author

Sam Northshield (samuel.northshield(AT)plattsburgh.edu), Aug 07 2006

Keywords

Comments

a(n) is the number of 'vectors' (..., e_k, e_{k-1}, ..., e_0) with e_k in {0,1,3} such that Sum_{k} e_k 2^k = n. a(2^n-1) = F(n+1)*a(2^{k+1}+j) + a(j) = a(2^k+j) + a(2^{k-1}+j) if 2^k > 4j. This sequence corresponds to the pair (3,1) as Stern's diatomic sequence [A002487] corresponds to (2,1) and Gould's sequence [A001316] corresponds to (1,1). There are many interesting similarities to A000119, the number of representations of n as a sum of distinct Fibonacci numbers.
A120562 can be generated from triangle A177444. Partial sums of A120562 = A177445. - Gary W. Adamson, May 08 2010
The Ca1 and Ca2 triangle sums, see A180662 for their definitions, of Sierpinski's triangle A047999 equal this sequence. Some A120562(2^n-p) sequences, 0 <= p <= 32, lead to known sequences, see the crossrefs. - Johannes W. Meijer, Jun 05 2011

Examples

			a(2^n)=1 since a(2n)=a(n).

Links

Crossrefs

Cf. A001316 (1,1), A002487 (2,1), A120562 (3,1), A112970 (4,1), A191373 (5,1).
Cf. A177444, A177445. - Gary W. Adamson, May 08 2010
Cf. A000012 (p=0), A000045 (p=1, p=2, p=4, p=8, p=16, p=32), A000071 (p=3, p=6, p=12, p=13, p=24, p=26), A001610 (p=5, p=10, p=20), A001595 (p=7, p=14, p=28), A014739 (p=11, p=22, p=29), A111314 (p=15, p=30), A027961 (p=19), A154691 (p=21), A001911 (p=23). - Johannes W. Meijer, Jun 05 2011
Same recurrence for odd n as A000930.

Programs

  • Maple
    p := product((1+x^(2^i)+x^(3*2^i)), i=0..25): s := series(p, x, 1000): for k from 0 to 250 do printf(`%d, `, coeff(s, x, k)) od:
A120562:=proc(n) option remember; if n <0 then A120562(n):=0 fi: if (n=0 or n=1) then 1 elif n mod 2 = 0 then A120562(n/2) else A120562((n-1)/2) + A120562((n-3)/2); fi; end: seq(A120562(n),n=0..64); # Johannes W. Meijer, Jun 05 2011
  • Mathematica
    a[0] = a[1] = 1; a[n_?EvenQ] := a[n] = a[n/2]; a[n_?OddQ] := a[n] = a[(n-1)/2] + a[(n-1)/2 - 1]; Table[a[n], {n, 0, 64}] (* Jean-François Alcover, Sep 29 2011 *)
Nest[Append[#1, If[EvenQ@ #2, #1[[#2/2 + 1]], Total@ #1[[#2 ;; #2 + 1]] & @@ {#1, (#2 - 1)/2}]] & @@ {#, Length@ #} &, {1, 1}, 10^4 - 1] (* Michael De Vlieger, Feb 19 2019 *)

Formula

Recurrence; a(0)=a(1)=1, a(2*n)=a(n) and a(2*n+1)=a(n)+a(n-1).
G.f.: A(x) = Product_{i>=0} (1 + x^(2^i) + x^(3*2^i)) = (1 + x + x^3)*A(x^2).
a(n-1) << n^x with x = log_2(phi) = 0.69424... - Charles R Greathouse IV, Dec 27 2011

Extensions

Reference edited and link added by Jason G. Wurtzel, Aug 22 2010
Showing 1-10 of 78 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.