A129100 -id:A129100 - cp's OEIS frontend

A030067 The "Semi-Fibonacci sequence": a(1) = 1; a(n) = a(n/2) (n even); a(n) = a(n-1) + a(n-2) (n odd).

1, 1, 2, 1, 3, 2, 5, 1, 6, 3, 9, 2, 11, 5, 16, 1, 17, 6, 23, 3, 26, 9, 35, 2, 37, 11, 48, 5, 53, 16, 69, 1, 70, 17, 87, 6, 93, 23, 116, 3, 119, 26, 145, 9, 154, 35, 189, 2, 191, 37, 228, 11, 239, 48, 287, 5, 292, 53, 345, 16, 361, 69, 430, 1, 431, 70, 501, 17, 518, 87, 605, 6, 611, 93

Offset: 1

David W. Wilson

This is the "semi-Fibonacci sequence". The distinct numbers that appear are called "semi-Fibonacci numbers", and are given in A030068.
a(2n+1) >= a(2n-1) + 1 is monotonically increasing. a(2n)/n can be arbitrarily small, as a(2^n) = 1. There are probably an infinite number of primes in the sequence. - Jonathan Vos Post, Mar 28 2006
From Robert G. Wilson v, Jan 17 2014: (Start)
Positions where k occurs:
   k: sequence
   -:-----------------------------
   1: A000079;
   2: 3*A000079 = A007283;
   3: 5*A000079 = A020714;
   4: none in the first 10^6 terms;
   5: 7*A000079 = A005009;
   6: 9*A000079 = A005010;
   7: none in the first 10^6 terms;
   8: none in the first 10^6 terms;
   9: 11*A000079 = A005015;
  10: none in the first 10^6 terms;
  11: 13*A000079 = A005029;
  12: none in the first 10^6 terms;
(End)
Any integer N which occurs in this sequence first occurs as an odd-indexed term a(2k-1) = A030068(k-1), and thereafter at indices (2k-1)*2^j, j=1,2,3,... (Both of these statements follow immediately from the definition of even-indexed terms.) No N can occur a second time as an odd-indexed term: This follows from the definition of these terms, a(2n+1) = a(2n) + a(2n-1) = a(2n-1) + a(n), which shows that the subsequence of odd-indexed terms (A030068) is strictly increasing, and therefore equal to the range (or: set) of the semi-Fibonacci numbers. - M. F. Hasler, Mar 24 2017
The lines in the logarithmic scatterplot of the sequence corresponds to sets of indices with the same 2-adic valuation. - Rémy Sigrist, Nov 27 2017
Define the partition subsum polynomial of an integer partition m of n where m = (m_1, m_2, ...m_k) by ps(m,x) = Product_{i=1..k} (1+x^m_i). Expanding ps(m,x) gives 1+a_1 x+a_2 x^2+...+a_n x^n, where a_j is the number of ways to form the subsum j from the parts of m. Then the number of partitions m of n for which ps(m,x) has no repeated root is a(n). - George Beck, Nov 07 2018

			a(1) = 1 by definition.
a(2) = a(1) = 1.
a(3) = 1 + 1 = 2.
a(4) = a(2) = 1.
a(5) = 2 + 1 = 3.
a(6) = a(3) = 2.
a(7) = 3 + 2 = 5.
a(8) = a(4) = 1.
a(9) = 5 + 1 = 6.
a(10) = a(5) = 3.

T. D. Noe, Table of n, a(n) for n = 1..10000
Abdulaziz M. Alanazi, Augustine O. Munagi and Darlison Nyirenda, Power Partitions and Semi-m-Fibonacci Partitions, arXiv:1910.09482 [math.CO], 2019.
George E. Andrews, Binary and Semi-Fibonacci Partitions, Journal of Ramanujan Society of Mathematics and Mathematics Sciences, honoring A.K. Agarwal's 70th birthday, 7:1(2019), 01-06.
Cristina Ballantine and George Beck, Partitions enumerated by self-similar sequences, arXiv:2303.11493 [math.CO], 2023.
George Beck, Semi-Fibonacci Partitions
Rémy Sigrist, Colored logarithmic scatterplot of the first 10000 terms (where the color is function of the 2-adic valuation of n)

Cf. A000045, A030068, A074364, A129092, A129100.

See A109671 for a variant.

import Data.List (transpose)
a030067 n = a030067_list !! (n-1)
a030067_list = concat $ transpose [scanl (+) 1 a030067_list, a030067_list]
-- Reinhard Zumkeller, Jul 21 2013, Jul 07 2013

f:=proc(n) option remember; if n=1 then RETURN(1) elif n mod 2 = 0 then RETURN(f(n/2)) else RETURN(f(n-1)+f(n-2)); fi; end;

semiFibo[1] = 1; semiFibo[n_?EvenQ] := semiFibo[n] = semiFibo[n/2]; semiFibo[n_?OddQ] := semiFibo[n] = semiFibo[n - 1] + semiFibo[n - 2]; Table[semiFibo[n], {n, 80}] (* Jean-François Alcover, Aug 19 2013 *)

a(n) = if(n==1, 1, if(n%2 == 0, a(n/2), a(n-1) + a(n-2)));
vector(100, n, a(n)) \\ Altug Alkan, Oct 12 2015

a=[1]; [a.append(a[-2]+a[-1] if n%2 else a[n//2-1]) for n in range(2, 75)]
print(a) # Michael S. Branicky, Jul 07 2022

Theorem: a(2n+1) - a(2n-1) = a(n). Proof: a(2n+1) - a(2n-1) = a(2n) + a(2n-1) - a(2n-2) - a(2n-3) = a(n) - a(n-1) + a(n-1) (induction) = a(n). - N. J. A. Sloane, May 02 2010
a(2^n - 1) = A129092(n) for n >= 1, where A129092 forms the row sums and column 0 of triangle A129100, which is defined by the nice property that column 0 of matrix power A129100^(2^k) = column k of A129100 for k > 0. - Paul D. Hanna, Dec 03 2008
G.f. g(x) satisfies (1-x^2) g(x) = (1+x-x^2) g(x^2) + x. - Robert Israel, Mar 23 2017

A129092 a(n) = A030067(2^n - 1) for n >= 1, where A030067 is the semi-Fibonacci numbers.

Original entry on oeis.org

1, 2, 5, 16, 69, 430, 4137, 64436, 1676353, 74555322, 5777029421, 792086153688, 194591768192733, 86534148901444102, 70244955881077121873, 104827174339054175240700, 289320796542222620694103961

Offset: 1

Paul D. Hanna, Mar 29 2007

nonn

			The semi-Fibonacci sequence (A030067) starts:
[(1), 1, (2), 1, 3, 2, (5), 1, 6, 3, 9, 2, 11, 5, (16), 1, ...],
and obeys the recurrence:
A030067(n) = A030067(n/2) when n is even; and
A030067(n) = A030067(n-1) + A030067(n-2) when n is odd.
This sequence also equals row sums of triangle A129100:
    1;
    1,    1;
    2,    2,    1;
    5,    6,    4,   1;
   16,   24,   20,   8,   1;
   69,  136,  136,  72,  16,  1;
  430, 1162, 1360, 880, 272, 32, 1; ...
where columns of A129100 shift left under matrix square,
so that A129100^2 starts:
     1;
     2,    1;
     6,    4,   1;
    24,   20,   8,   1;
   136,  136,  72,  16,  1;
  1162, 1360, 880, 272, 32, 1; ...

Cf. A030067, A129093, A129094.

/* Generated as column 0 of triangle A129100: */ a(n)=local(A=Mat(1),B);for(m=1,n+1,B=matrix(m,m);for(r=1,m,for(c=1,r, if(r==c || r==1 || r==2,B[r,c]=1,if(c==1,B[r,1]=sum(i=1,r-1,A[r-1,i]), B[r,c]=(A^(2^(c-1)))[r-c+1,1])); )); A=B); return(A[n+1,1])

Equals the row sums and first column of triangle A129100: a(n) = A129100(n,0), where column 0 of matrix power A129100^(2^k) = column k of A129100 for k > 0.

A129093 a(n) = A030067(2^(n+1) - 3) for n>=1, where A030067 is the semi-Fibonacci numbers.

Original entry on oeis.org

1, 3, 11, 53, 361, 3707, 60299, 1611917, 72878969, 5702474099, 786309124267, 193799682039045, 86339557133251369, 70158421732175677771, 104756929383173098118827, 289215969367883566518863261

Offset: 1

Paul D. Hanna, Mar 29 2007

nonn

			This sequence also equals the row sums of the triangle formed from the semi-Fibonacci numbers (A030067) with 2^n terms in row n for n>=0:
n=0: 1;
n=1: 1, 2;
n=2: 1, 3, 2, 5;
n=3: 1, 6, 3, 9, 2, 11, 5, 16;
n=4: 1, 17, 6, 23, 3, 26, 9, 35, 2, 37, 11, 48, 5, 53, 16, 69; ...
and the rightmost border equals A129092(n) = A030067(2^n - 1).
The semi-Fibonacci numbers (A030067) start:
[1, (1), 2, 1, (3), 2, 5, 1, 6, 3, 9, 2, (11), 5, 16, 1, ...],
and obey the recurrence:
A030067(n) = A030067(n/2) when n is even; and
A030067(n) = A030067(n-1) + A030067(n-2) when n is odd.
This sequence also equals row sums of matrix square A129100^2:
1;
2, 1;
6, 4, 1;
24, 20, 8, 1;
136, 136, 72, 16, 1;
1162, 1360, 880, 272, 32, 1; ...

Cf. A030067, A129092, A129094.

/* As row sums of the matrix square of triangle A129100: */
a(n)=local(A=Mat(1),B);for(m=1,n+1,B=matrix(m,m);for(r=1,m,for(c=1,r, if(r==c || r==1 || r==2, B[r,c]=1, if(c==1, B[r,1]=sum(i=1,r-1,A[r-1,i]), B[r,c]=(A^(2^(c-1)))[r-c+1,1])))); A=B); sum(k=1,n,(A^2)[n,k])
for(n=1,20,print1(a(n),", "))

Equals the first differences of A129092: a(n) = A129092(n+1) - A129092(n).

Equals the row sums of the matrix square of triangle A129100.

A129104 Triangle T, read by rows, where row n (shifted left) of T equals row 0 of matrix power T^n for n>=0.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 5, 6, 4, 1, 1, 16, 24, 20, 8, 1, 1, 69, 136, 136, 72, 16, 1, 1, 430, 1162, 1360, 880, 272, 32, 1, 1, 4137, 15702, 21204, 16032, 6240, 1056, 64, 1, 1, 64436, 346768, 537748, 461992, 214336, 46784, 4160, 128, 1, 1, 1676353, 12836904

Offset: 0

Paul D. Hanna, Apr 14 2007

This irregular-shaped triangle T results from inserting a left column of all 1's into triangle A129100; curiously, column k of A129100 equals column 0 of matrix power A129100^(2^k), while row n of A129100 equals row 0 of matrix power T^n (T is this triangle).

			Triangle T begins:
1, 1;
1, 1, 1;
1, 2, 2, 1;
1, 5, 6, 4, 1;
1, 16, 24, 20, 8, 1;
1, 69, 136, 136, 72, 16, 1; ...
where row 0 of matrix power T^k forms row k of T shift left,
as illustrated below.
For row 2: the matrix square T^2 begins:
2, 2, 1;
3, 4, 3, 1;
6, 12, 12, 6, 1;
17, 54, 65, 42, 12, 1;
70, 362, 512, 400, 156, 24, 1;
431, 3708, 6223, 5656, 2744, 600, 48, 1; ...
and row 0 of T^2 equals row 2 of T shift left: [2, 2, 1].
For row 3: the matrix cube T^3 begins:
5, 6, 4, 1;
11, 18, 16, 7, 1;
37, 88, 96, 56, 14, 1;
191, 672, 860, 609, 210, 28, 1;
1525, 8038, 11956, 9856, 4256, 812, 56, 1; ...
and row 0 of T^3 equals row 3 of T shift left: [5, 6, 4, 1].
For row 4: T^4 begins:
16, 24, 20, 8, 1;
53, 112, 116, 64, 15, 1;
292, 890, 1088, 736, 240, 30, 1;
2571, 11350, 16056, 12664, 5185, 930, 60, 1; ...
and row 0 of T^4 equals row 4 of T shift left: [16, 24, 20, 8, 1].

Cf. A030067 (Semi-Fibonacci); A129092 (column 1), A129101 (column 2), A129102 (column 3), A129103 (column 4); variant: A129100.

T(n,k)=local(A=[1,1;1,1],B);for(m=1,n+1,B=matrix(m+1,m+1); for(r=1,m,for(c=1,r+1,if(r==c-1 || c==1,B[r,c]=1, B[r,c]=(A^(r-1))[1,c-1])));A=B); return(A[n+1, k+1])

Column 1: T(n,1) = A129092(n) = A030067(2^n - 1) for n>=1, where A030067 is the semi-Fibonacci numbers.

cp's OEIS Frontend

A129101 Column 1 of triangle A129100; also equals column 0 of the matrix square of A129100.

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A129102 Column 2 of triangle A129100; also equals column 0 of matrix power A129100^4.

Views

Author

Keywords

Crossrefs

Programs

PARI

A129103 Column 3 of triangle A129100; also equals column 0 of matrix power A129100^8.

Views

Author

Keywords

Crossrefs

Programs

PARI

A030067 The "Semi-Fibonacci sequence": a(1) = 1; a(n) = a(n/2) (n even); a(n) = a(n-1) + a(n-2) (n odd).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A129092 a(n) = A030067(2^n - 1) for n >= 1, where A030067 is the semi-Fibonacci numbers.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A129093 a(n) = A030067(2^(n+1) - 3) for n>=1, where A030067 is the semi-Fibonacci numbers.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A129104 Triangle T, read by rows, where row n (shifted left) of T equals row 0 of matrix power T^n for n>=0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula