A109671 -id:A109671 - cp's OEIS frontend

A169745 Numbers k such that A109671(2*k+1) = 1.

0, 2, 5, 11, 18, 21, 23, 35, 39, 44, 47, 66, 69, 72, 75, 81, 87, 89, 95, 131, 141, 147, 153, 159, 165, 174, 176, 179, 186, 189, 191, 258, 261, 264, 267, 275, 278, 281, 285, 291, 297, 303, 315, 320, 323, 329, 342, 345, 347, 350, 353, 359, 371, 375, 380, 383, 515, 546, 549, 557

Offset: 1

N. J. A. Sloane, May 02 2010

nonn

N. J. A. Sloane, Table of n, a(n) for n = 1..9710

Cf. A109671, A169743, A169744, A169746 (first differences).

A169741 a(n) = smallest k such that A109671(k)=n, or -1 if n does not appear in A109671.

Original entry on oeis.org

1, 3, 7, 39, 17, 15, 169, 33, 31, 135, 313, 231, 337, 1257, 113, 1341, 65, 63, 1043, 1077, 937, 4137, 625, 225, 673, 129, 127, 519, 2057, 903, 2099, 2157, 1849, 2493, 2167, 999, 1081, 2685, 1873, 8277, 1249, 7401, 1343, 8289, 497, 8349, 1079, 5373, 4139, 16827

Offset: 1

N. J. A. Sloane, May 02 2010

nonn

Zak Seidov, Table of n, a(n) for n = 1..2443

# Define A109671:
f:=proc(n) option remember; local t1;
if n = 1 then RETURN(1);
elif n mod 2 = 0 then RETURN(f(n/2));
else t1:= f(n-2)-f((n-1)/2);
if t1 > 0 then RETURN(t1) else RETURN(f(n-2)+f((n-1)/2)); fi; fi; end;
# Compute A169741:
M:=50000: M2:=100;
b1:=[seq(f(n),n=1..M)]: b2:=array(1..M);
for n from 1 to M do b2[n]:=-1; od:
for n from 1 to M do i:=b1[n]; if b2[i]<0 then b2[i]:=n; fi; od:
[seq(b2[i],i=1..M2)];

A169743 Numbers k such that A109671(k) = 1.

Original entry on oeis.org

1, 2, 4, 5, 8, 10, 11, 16, 20, 22, 23, 32, 37, 40, 43, 44, 46, 47, 64, 71, 74, 79, 80, 86, 88, 89, 92, 94, 95, 128, 133, 139, 142, 145, 148, 151, 158, 160, 163, 172, 175, 176, 178, 179, 184, 188, 190, 191, 256, 263, 266, 278, 283, 284, 290, 295, 296, 302, 307, 316, 319, 320

Offset: 1

N. J. A. Sloane, May 02 2010

nonn

If m is a term so is 2m.

Cf. A109671, A169744, A169745.

A169744 Odd numbers n such that A109671(n) = 1.

Original entry on oeis.org

1, 5, 11, 23, 37, 43, 47, 71, 79, 89, 95, 133, 139, 145, 151, 163, 175, 179, 191, 263, 283, 295, 307, 319, 331, 349, 353, 359, 373, 379, 383, 517, 523, 529, 535, 551, 557, 563, 571, 583, 595, 607, 631, 641, 647, 659, 685, 691, 695, 701, 707, 719, 743, 751, 761, 767, 1031, 1093

Offset: 1

N. J. A. Sloane, May 02 2010

nonn

Cf. A109671, A169743, A169745.

A169742 A109671(2n+1).

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 3, 6, 5, 3, 2, 1, 3, 6, 3, 9, 8, 3, 1, 4, 3, 1, 2, 1, 3, 6, 3, 9, 6, 3, 9, 18, 17, 9, 4, 1, 3, 2, 5, 1, 2, 5, 3, 2, 1, 3, 2, 1, 3, 6, 3, 9, 6, 3, 9, 18, 15, 9, 6, 3, 9, 18, 9, 27, 26, 9, 1, 10, 5, 1, 4, 3, 1, 4, 3, 1, 4, 9, 5, 4, 3, 1, 4, 9, 7, 4, 3, 1, 2, 1, 3, 6, 5, 3, 2, 1, 3, 6, 3, 9, 6, 3

Offset: 0

N. J. A. Sloane, May 02 2010

nonn

The other bisection of A109671 is of course A109671 again.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000

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

Original entry on oeis.org

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

Offset: 1

David W. Wilson

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

			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.

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

Cf. A000045, A030068, A074364, A129092, A129100.

See A109671 for a variant.

import Data.List (transpose)
a030067 n = a030067_list !! (n-1)
a030067_list = concat $ transpose [scanl (+) 1 a030067_list, a030067_list]
-- Reinhard Zumkeller, Jul 21 2013, Jul 07 2013

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;

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

a(n) = if(n==1, 1, if(n%2 == 0, a(n/2), a(n-1) + a(n-2)));
vector(100, n, a(n)) \\ Altug Alkan, Oct 12 2015

a=[1]; [a.append(a[-2]+a[-1] if n%2 else a[n//2-1]) for n in range(2, 75)]
print(a) # Michael S. Branicky, Jul 07 2022

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

A169746 First differences of A169745.

Original entry on oeis.org

2, 3, 6, 7, 3, 2, 12, 4, 5, 3, 19, 3, 3, 3, 6, 6, 2, 6, 36, 10, 6, 6, 6, 6, 9, 2, 3, 7, 3, 2, 67, 3, 3, 3, 8, 3, 3, 4, 6, 6, 6, 12, 5, 3, 6, 13, 3, 2, 3, 3, 6, 12, 4, 5, 3, 132, 31, 3, 8, 9, 3, 4, 9, 3, 6, 6, 9, 3, 6, 15, 2, 3, 3, 3, 7, 2, 3, 9, 3, 4, 14, 10, 3, 3, 2, 6, 7, 3, 2, 19, 3, 3, 3, 6, 6, 2, 6, 259

Offset: 1

N. J. A. Sloane, May 03 2010

nonn

N. J. A. Sloane, Table of n, a(n) for n = 1..9709

Cf. A109671, A169745.

A169747 a(1)=1; thereafter, a(2n)=a(n), a(2n+1) = a(2n-1)-a(n) if that number is positive and not already in the sequence, otherwise a(2n+1) = a(2n-1)+a(n).

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 5, 1, 4, 3, 7, 2, 9, 5, 14, 1, 13, 4, 17, 3, 20, 7, 27, 2, 25, 9, 16, 5, 11, 14, 25, 1, 24, 13, 37, 4, 33, 17, 50, 3, 47, 20, 67, 7, 60, 27, 87, 2, 85, 25, 110, 9, 101, 16, 117, 5, 112, 11, 123, 14, 109, 25, 84, 1, 83, 24, 59, 13, 46, 37, 83, 4, 79, 33, 112, 17, 95

Offset: 1

N. J. A. Sloane, May 02 2010

nonn

Suggested by A005132, A030067, A109671.

Zak Seidov, Table of n, a(n) for n = 1..1000. - _Zak Seidov_, May 04 2010

a={1,1};Do[c=If[EvenQ[n],a[[n/2]],If[(b=a[[n-2]]-a[[(n-1)/2]])>0&&FreeQ[a,b],b,a[[n-2]]+a[[(n-1)/2]]]];AppendTo[a,c],{n,3,1000}];a (* Zak Seidov, May 04 2010 *)

More terms from Zak Seidov, May 04 2010

A288310 a(0) = a(1) = 1; a(2n) = a(n) - a(n-1), a(2n+1) = Sum_{k=0..n} a(n-k).

Original entry on oeis.org

1, 1, 0, 2, -1, 2, 2, 4, -3, 3, 3, 5, 0, 7, 2, 11, -7, 8, 6, 11, 0, 14, 2, 19, -5, 19, 7, 26, -5, 28, 9, 39, -18, 32, 15, 40, -2, 46, 5, 57, -11, 57, 14, 71, -12, 73, 17, 92, -24, 87, 24, 106, -12, 113, 19, 139, -31, 134, 33, 162, -19, 171, 30, 210, -57, 192, 50, 224, -17, 239, 25

Offset: 0

Ilya Gutkovskiy, Jun 07 2017

sign

Sequence has its first differences and its partial sums as bisections.

			a(0) = a(1) = 1 by definition;
a(2) = a(2*1) = a(1) - a(0) = 0;
a(3) = a(2*1+1) = a(0) + a(1) = 2;
a(4) = a(2*2) = a(2) - a(1) = -1;
a(5) = a(2*2+1) = a(0) + a(1) + a(2) = 2;
a(6) = a(2*3) = a(3) - a(2) = 2, etc.

Michael Gilleland, Some Self-Similar Integer Sequences

Cf. A030067, A086449, A086450, A109671.

a[0] = 1; a[1] = 1; a[n_] := a[n] = If[EvenQ[n], a[n/2] - a[(n - 2)/2], Sum[a[(n - 1)/2 - k], {k, 0, (n - 1)/2}]]; Table[a[n], {n, 0, 70}]

def a(n): return 1 if n<2 else a(n/2) - a(n/2 - 1) if n%2==0 else sum([a((n - 1)/2 - k) for k in range((n + 1)/2)]) # Indranil Ghosh, Jun 08 2017

a(n) = Sum_{k=0..n} a(2*k).
a(n) = a(2*n+1) - a(2*n-1).
a(2*n+1) = Sum_{k=0..n} Sum_{m=0..k} a(2*m).

cp's OEIS Frontend

A169745 Numbers k such that A109671(2*k+1) = 1.

Views

Author

Keywords

Links

Crossrefs

A169741 a(n) = smallest k such that A109671(k)=n, or -1 if n does not appear in A109671.

Views

Author

Keywords

Links

Programs

Maple

A169743 Numbers k such that A109671(k) = 1.

Views

Author

Keywords

Comments

Crossrefs

A169744 Odd numbers n such that A109671(n) = 1.

Views

Author

Keywords

Crossrefs

A169742 A109671(2n+1).

Views

Author

Keywords

Comments

Links

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A169746 First differences of A169745.

Views

Author

Keywords

Links

Crossrefs

A169747 a(1)=1; thereafter, a(2n)=a(n), a(2n+1) = a(2n-1)-a(n) if that number is positive and not already in the sequence, otherwise a(2n+1) = a(2n-1)+a(n).

Views

Author

Keywords

Comments

Links

Programs

Mathematica

Extensions

A288310 a(0) = a(1) = 1; a(2*n) = a(n) - a(n-1), a(2*n+1) = Sum_{k=0..n} a(n-k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A288310 a(0) = a(1) = 1; a(2n) = a(n) - a(n-1), a(2n+1) = Sum_{k=0..n} a(n-k).