

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
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 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

T. D. Noe, Table of n, a(n) for n = 1..10000
Abdulaziz M. Alanazi, Augustine O. Munagi and Darlison Nyirenda, Power Partitions and SemimFibonacci Partitions, arXiv:1910.09482 [math.CO], 2019.
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.
George Beck, SemiFibonacci Partitions
Rémy Sigrist, Colored logarithmic scatterplot of the first 10000 terms (where the color is function of the 2adic valuation of n)


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]
 Reinhard Zumkeller, Jul 21 2013, Jul 07 2013
(PARI) a(n) = if(n==1, 1, if(n%2 == 0, a(n/2), a(n1) + a(n2)));
vector(100, n, a(n)) \\ Altug Alkan, Oct 12 2015
(Python)
a=[1]; [a.append(a[2]+a[1] if n%2 else a[n//21]) for n in range(2, 75)]
print(a) # Michael S. Branicky, Jul 07 2022


CROSSREFS

Cf. A000045, A030068, A074364, A129092, A129100.
See A109671 for a variant.
Sequence in context: A332819 A321272 A321270 * A181363 A105800 A105602
Adjacent sequences: A030064 A030065 A030066 * A030068 A030069 A030070


KEYWORD

nonn,nice,look


AUTHOR

David W. Wilson


STATUS

approved



