

A030067


The "SemiFibonacci sequence": a(1) = 1; a(n) = a(n/2) (n even); a(n) = a(n1) + a(n2) (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 "semiFibonacci sequence". The distinct numbers that appear are called "semiFibonacci numbers", and are given in A030068.
a(2n+1) >= a(2n1) + 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 oddindexed term a(2k1) = A030068(k1), and thereafter at indices (2k1)*2^j, j=1,2,3,... (Both of these statements follow immediately from the definition of evenindexed terms.) No N can occur a second time as an oddindexed term: This follows from the definition of these terms, a(2n+1) = a(2n) + a(2n1) = a(2n1) + a(n), which shows that the subsequence of oddindexed terms (A030068) is strictly increasing, and therefore equal to the range (or: set) of the semiFibonacci numbers.  M. F. Hasler, Mar 24 2017
The lines in the logarithmic scatterplot of the sequence corresponds to sets of indices with the same 2adic 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 SemiFibonacci Partitions, Journal of Ramanujan Society of Mathematics and Mathematics Sciences, honoring A.K. Agarwal's 70th birthday), 7:1(2019), 0106.


FORMULA

Theorem: a(2n+1)  a(2n1) = a(n). Proof: a(2n+1)  a(2n1) = a(2n) + a(2n1)  a(2n2)  a(2n3) = a(n)  a(n1) + a(n1) (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 (1x^2) g(x) = (1+xx^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(n1)+f(n2)); 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}] (* JeanFrançois Alcover, Aug 19 2013 *)


PROG

(Haskell)
import Data.List (transpose)
a030067 n = a030067_list !! (n1)
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(n1) + a(n2)));
(Python)
a=[1]; [a.append(a[2]+a[1] if n%2 else a[n//21]) for n in range(2, 75)]


CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



