

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:
1: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, ..., = A000079;
2: 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, ..., = 3*A000079 = A007283;
3: 5, 10, 20, 40, 80, 160, 320, 640, 1280, 2560, 5120, 10240, ..., = 5*A000079 = A020714;
4: none in the first 10^6 terms;
5: 7, 14, 28, 56, 112, 224, 448, 896, 1792, 3584, 7168, 14336, ..., = 7*A000079 = A005009;
6: 9, 18, 36, 72, 144, 288, 576, 1152, 2304, 4608, 9216, 18432, ..., = 9*A000079 = A005010;
7: none in the first 10^6 terms;
8: none in the first 10^6 terms;
9: 11, 22, 44, 88, 176, 352, 704, 1408, 2816, 5632, 11264, 22528, ..., = 11*A000079 = A005015;
10: none in the first 10^6 terms;
11: 13, 26, 52, 104, 208, 416, 832, 1664, 3328, 6656, 13312, 26624, ..., = 13*A000079 = A005029;
12: none in the first 10^6 terms;
Values that A030067 takes: 1, 2, 3, 5, 6, 9, 11, 16, 17, 23, 26, 35, 37, 48, ..., = A030068.
(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


LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000


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


CROSSREFS

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


KEYWORD

nonn,nice,look


AUTHOR

David W. Wilson


STATUS

approved



