%I #85 Aug 06 2024 02:42:38
%S 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,
%T 16,69,1,70,17,87,6,93,23,116,3,119,26,145,9,154,35,189,2,191,37,228,
%U 11,239,48,287,5,292,53,345,16,361,69,430,1,431,70,501,17,518,87,605,6,611,93
%N The "Semi-Fibonacci sequence": a(1) = 1; a(n) = a(n/2) (n even); a(n) = a(n-1) + a(n-2) (n odd).
%C This is the "semi-Fibonacci sequence". The distinct numbers that appear are called "semi-Fibonacci numbers", and are given in A030068.
%C 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
%C From _Robert G. Wilson v_, Jan 17 2014: (Start)
%C Positions where k occurs:
%C k: sequence
%C -:-----------------------------
%C 1: A000079;
%C 2: 3*A000079 = A007283;
%C 3: 5*A000079 = A020714;
%C 4: none in the first 10^6 terms;
%C 5: 7*A000079 = A005009;
%C 6: 9*A000079 = A005010;
%C 7: none in the first 10^6 terms;
%C 8: none in the first 10^6 terms;
%C 9: 11*A000079 = A005015;
%C 10: none in the first 10^6 terms;
%C 11: 13*A000079 = A005029;
%C 12: none in the first 10^6 terms;
%C (End)
%C 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
%C 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
%C 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
%H T. D. Noe, <a href="/A030067/b030067.txt">Table of n, a(n) for n = 1..10000</a>
%H Abdulaziz M. Alanazi, Augustine O. Munagi and Darlison Nyirenda, <a href="https://arxiv.org/abs/1910.09482">Power Partitions and Semi-m-Fibonacci Partitions</a>, arXiv:1910.09482 [math.CO], 2019.
%H George E. Andrews, <a href="https://georgeandrews1.github.io/pdf/Binary%20and%20Semi-Fibonnaci.pdf">Binary and Semi-Fibonacci Partitions</a>, Journal of Ramanujan Society of Mathematics and Mathematics Sciences, honoring A.K. Agarwal's 70th birthday, 7:1(2019), 01-06.
%H Cristina Ballantine and George Beck, <a href="https://arxiv.org/abs/2303.11493">Partitions enumerated by self-similar sequences</a>, arXiv:2303.11493 [math.CO], 2023.
%H George Beck, <a href="http://demonstrations.wolfram.com/SemiFibonacciPartitions/">Semi-Fibonacci Partitions</a>
%H Rémy Sigrist, <a href="/A030067/a030067.png">Colored logarithmic scatterplot of the first 10000 terms</a> (where the color is function of the 2-adic valuation of n)
%F 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
%F 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
%F G.f. g(x) satisfies (1-x^2) g(x) = (1+x-x^2) g(x^2) + x. - _Robert Israel_, Mar 23 2017
%e a(1) = 1 by definition.
%e a(2) = a(1) = 1.
%e a(3) = 1 + 1 = 2.
%e a(4) = a(2) = 1.
%e a(5) = 2 + 1 = 3.
%e a(6) = a(3) = 2.
%e a(7) = 3 + 2 = 5.
%e a(8) = a(4) = 1.
%e a(9) = 5 + 1 = 6.
%e a(10) = a(5) = 3.
%p 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;
%t 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 *)
%o (Haskell)
%o import Data.List (transpose)
%o a030067 n = a030067_list !! (n-1)
%o a030067_list = concat $ transpose [scanl (+) 1 a030067_list, a030067_list]
%o -- _Reinhard Zumkeller_, Jul 21 2013, Jul 07 2013
%o (PARI) a(n) = if(n==1, 1, if(n%2 == 0, a(n/2), a(n-1) + a(n-2)));
%o vector(100, n, a(n)) \\ _Altug Alkan_, Oct 12 2015
%o (Python)
%o a=[1]; [a.append(a[-2]+a[-1] if n%2 else a[n//2-1]) for n in range(2, 75)]
%o print(a) # _Michael S. Branicky_, Jul 07 2022
%Y Cf. A000045, A030068, A074364, A129092, A129100.
%Y See A109671 for a variant.
%K nonn,nice,look
%O 1,3
%A _David W. Wilson_