login
a(n) = a(n-1) + a(floor(n/2)), a(1) = 1.
(Formerly N0236)
36

%I N0236 #88 Oct 10 2024 16:06:22

%S 1,2,3,5,7,10,13,18,23,30,37,47,57,70,83,101,119,142,165,195,225,262,

%T 299,346,393,450,507,577,647,730,813,914,1015,1134,1253,1395,1537,

%U 1702,1867,2062,2257,2482,2707,2969,3231,3530,3829,4175,4521,4914,5307,5757

%N a(n) = a(n-1) + a(floor(n/2)), a(1) = 1.

%C Sequence gives the number of partitions of 2n into "strongly decreasing" parts (see the function s*(n) in the paper by Bessenrodt, Olsson, and Sellers); see the example in A040039.

%C a(A036554(n)) is even, a(A003159(n)) is odd. - _Benoit Cloitre_, Oct 23 2002

%C Partial sums of the sequence a(1)=1, a(1), a(1), a(2), a(2), a(3), a(3), a(4), a(4), a(5), a(5), a(6), ...; example: a(1) = 1, a(2) = 1+1 = 2, a(3) = 1+1+1 = 3, a(4) = 1+1+1+2 = 5, a(5) = 1+1+1+2+2 = 7, ... - _Philippe Deléham_, Jan 02 2004

%C The number of odd numbers before the n-th even number in this sequence is A003156(n). - _Philippe Deléham_, Mar 27 2004

%C There are no terms divisible by 4 and there are infinitely many terms divisible by {2,3,5,6,7,9,10,11,13,14,15} (see van Doorn link). - _Ivan N. Ianakiev_, Aug 06 2022 and _Wouter van Doorn_, Sep 17 2024

%C a(n) = A001401(n), for 1..14. A001401(15) = 84. - _Wolfdieter Lang_, Jan 09 2023

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%H T. D. Noe, <a href="/A033485/b033485.txt">Table of n, a(n) for n=1..1000</a>

%H J. Arkin, <a href="http://www.fq.math.ca/Scanned/9-2/advanced9-2-a.pdf">Problem H-102: Gone but not forgotten</a>, Fibonacci Quarterly, Vol. 9 (1971), page 135.

%H Christine Bessenrodt, Jorn B. Olsson, and James A. Sellers, <a href="http://arxiv.org/abs/1107.1156">Unique path partitions: Characterization and Congruences</a>, arXiv:1107.1156 [math.CO], 2011-2012.

%H Philippe Deléham, <a href="/A033485/a033485.pdf">Letter to N. J. A. Sloane, Apr 20 1998</a>

%H William Gasarch, <a href="https://blog.computationalcomplexity.org/2022/07/what-is-known-about-that-sequence.html">What is known about that sequence</a>, Computational Complexity blog, Jul 20 2022.

%H Wouter van Doorn, <a href="https://arxiv.org/abs/2406.09532">On the congruence properties and growth rate of a recursively defined sequence</a>, arXiv:2406.09532 [math.NT], 2024.

%F a(n) = A000123(n)/2, for n >= 1.

%F Conjecture: lim_{n->oo} a(2n)/a(n)*log(n)/n = c = 1.64.... and a(n)/A(n) is bounded where A(n)=1 if n is a power of 2, otherwise A(n) = sqrt(n)*Product_{k<log_2(n)} n/2^k/log(n/2^k)). - _Benoit Cloitre_, Jan 26 2003

%F G.f.: A(x) satisfies x + (1+x)*A(x^2) = (1-x)*A(x). a(n) modulo 2 = A035263(n). - _Philippe Deléham_, Feb 25 2004

%F G.f.: (1/2)*(((1-x)*Product_{n>=0} (1-x^(2^n)))^(-1)-1). a(n) modulo 4 = A007413(n). - _Philippe Deléham_, Feb 28 2004

%F Sum_{k=1..n} a(k) = (a(2n+1)-1)/2 = A178855(n). - _Philippe Deléham_, Mar 18 2004

%F a(2n-1) = A131205(n). - _Jean-Paul Allouche_, Aug 11 2021

%F There exists a function f(n) such that n^f(n) < a(n) < n^(f(n) + epsilon) for all epsilon > 0 and all large enough n. - _Wouter van Doorn_, Sep 17 2024

%p a:= proc(n) option remember;

%p `if`(n<2, n, a(n-1)+a(iquo(n, 2)))

%p end:

%p seq(a(n), n=1..60); # _Alois P. Heinz_, Dec 16 2019

%t b[1]=1; b[n_] := b[n]=Sum[b[k], {k, 1, n/2}]; Table[b[n], {n, 3, 105, 2}] (* _Robert G. Wilson v_, Apr 22 2001 *)

%o (PARI) a(n)=if(n<2,1,a(floor(n/2))+a(n-1))

%o (Haskell)

%o import Data.List (transpose)

%o a033485 n = a033485_list !! (n-1)

%o a033485_list = 1 : zipWith (+)

%o a033485_list (concat $ transpose [a033485_list, a033485_list])

%o -- _Reinhard Zumkeller_, Nov 15 2012

%o (Magma) [n le 1 select 1 else Self(n-1) + Self(Floor(n/2)) : n in [1..60]]; // _Vincenzo Librandi_, Nov 20 2015

%o (Python)

%o from itertools import islice

%o from collections import deque

%o def A033485_gen(): # generator of terms

%o aqueue, f, b, a = deque([2]), True, 1, 2

%o yield from (1, 2)

%o while True:

%o a += b

%o yield a

%o aqueue.append(a)

%o if f: b = aqueue.popleft()

%o f = not f

%o A033485_list = list(islice(A033485_gen(),40)) # _Chai Wah Wu_, Jun 07 2022

%Y Cf. A040039 (first differences), A178855 (partial sums).

%Y Also half of A000123 (with first term omitted).

%Y Cf. A022907.

%Y Cf. A036554, A003159, A003156.

%Y Cf. A007413, A178855, A131205.

%K nonn,nice,easy

%O 1,2

%A _N. J. A. Sloane_. This was in the 1973 "Handbook", but was then dropped from the database. Resubmitted by _Philippe Deléham_. Entry revised by _N. J. A. Sloane_, Jun 10 2012