|
| |
|
|
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).
|
|
18
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
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
Positions where k occurs:
k: sequence
-:-----------------------------
4: none in the first 10^6 terms;
7: none in the first 10^6 terms;
8: none in the first 10^6 terms;
10: none in the first 10^6 terms;
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
|
|
|
LINKS
|
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.
|
|
|
FORMULA
|
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
|
|
|
EXAMPLE
|
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.
|
|
|
MAPLE
|
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;
|
|
|
MATHEMATICA
|
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 *)
|
|
|
PROG
|
(Haskell)
import Data.List (transpose)
a030067 n = a030067_list !! (n-1)
a030067_list = concat $ transpose [scanl (+) 1 a030067_list, a030067_list]
(PARI) a(n) = if(n==1, 1, if(n%2 == 0, a(n/2), a(n-1) + a(n-2)));
(Python)
a=[1]; [a.append(a[-2]+a[-1] if n%2 else a[n//2-1]) for n in range(2, 75)]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
