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

1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70, 83, 101, 119, 142, 165, 195, 225, 262, 299, 346, 393, 450, 507, 577, 647, 730, 813, 914, 1015, 1134, 1253, 1395, 1537, 1702, 1867, 2062, 2257, 2482, 2707, 2969, 3231, 3530, 3829, 4175, 4521, 4914, 5307, 5757

Offset: 1

Author

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

Keywords

• nonn
• nice
• easy

Comments

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.

a(A036554(n)) is even, a(A003159(n)) is odd. - Benoit Cloitre, Oct 23 2002

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

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

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

a(n) = A001401(n), for 1..14. A001401(15) = 84. - Wolfdieter Lang, Jan 09 2023

References

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

Links

• T. D. Noe, Table of n, a(n) for n=1..1000
• J. Arkin, Problem H-102: Gone but not forgotten, Fibonacci Quarterly, Vol. 9 (1971), page 135.
• Christine Bessenrodt, Jorn B. Olsson, and James A. Sellers, Unique path partitions: Characterization and Congruences, arXiv:1107.1156 [math.CO], 2011-2012.
• Philippe Deléham, Letter to N. J. A. Sloane, Apr 20 1998
• William Gasarch, What is known about that sequence, Computational Complexity blog, Jul 20 2022.
• Wouter van Doorn, On the congruence properties and growth rate of a recursively defined sequence, arXiv:2406.09532 [math.NT], 2024.

Crossrefs

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

Also half of A000123 (with first term omitted).

Cf. A022907.

Cf. A036554, A003159, A003156.

Cf. A007413, A178855, A131205.

Programs

Haskell

import Data.List (transpose)
a033485 n = a033485_list !! (n-1)
a033485_list = 1 : zipWith (+)
   a033485_list (concat $ transpose [a033485_list, a033485_list])
-- Reinhard Zumkeller, Nov 15 2012

Magma

[n le 1 select 1 else Self(n-1) + Self(Floor(n/2)) : n in [1..60]]; // Vincenzo Librandi, Nov 20 2015

Maple

a:= proc(n) option remember;
      `if`(n<2, n, a(n-1)+a(iquo(n, 2)))
    end:
seq(a(n), n=1..60);  # Alois P. Heinz, Dec 16 2019

Mathematica

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

PARI

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

Python

from itertools import islice
from collections import deque
def A033485_gen(): # generator of terms
    aqueue, f, b, a = deque([2]), True, 1, 2
    yield from (1, 2)
    while True:
        a += b
        yield a
        aqueue.append(a)
        if f: b = aqueue.popleft()
        f = not f
A033485_list = list(islice(A033485_gen(),40)) # Chai Wah Wu, Jun 07 2022

Formula

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

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_{kBenoit Cloitre, Jan 26 2003

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

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

Sum_{k=1..n} a(k) = (a(2n+1)-1)/2 = A178855(n). - Philippe Deléham, Mar 18 2004

a(2n-1) = A131205(n). - Jean-Paul Allouche, Aug 11 2021

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