A005230 Stern's sequence: a(1) = 1, a(n+1) is the sum of the m preceding terms, where m*(m-1)/2 < n <= m*(m+1)/2 or equivalently m = ceiling((sqrt(8*n+1)-1)/2) = A002024(n).

1, 1, 2, 3, 6, 11, 20, 40, 77, 148, 285, 570, 1120, 2200, 4323, 8498, 16996, 33707, 66844, 132568, 262936, 521549, 1043098, 2077698, 4138400, 8243093, 16419342, 32706116, 65149296, 130298592, 260075635, 519108172, 1036138646, 2068138892, 4128034691

Offset: 1

Author

N. J. A. Sloane, Simon Plouffe

Keywords

• core
• easy
• nonn
• nice

Comments

A002487 is THE Stern's sequence!

Limit_{n->oo} a(n)/2^n = 0.11756264240558743281779408719593950494049225979176... - Jon E. Schoenfield, Dec 17 2016

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Harvey P. Dale, Table of n, a(n) for n = 1..1000 [extending prior submission by T. D. Noe]
• Jaegug Bae and Sungjin Choi, A generalization of a subset-sum-distinct sequence, J. Korean Math. Soc. 40 (2003), no. 5, 757-768. MR1996839 (2004d:05198). See d_1(n).
• G. Kreweras, Sur quelques problèmes relatifs au vote pondéré, [Some problems of weighted voting], Math. Sci. Humaines No. 84 (1983), 45-63.
• M. A. Stern, Aufgaben, J. Reine Angew. Math., 18 (1838), 100.
• Index entries for sequences related to Stern's sequences
• Index entries for "core" sequences

Crossrefs

Cf. A002487.

Programs

Maple

A005230[1] := 1: n := 50: for k from 1 to n-1 do: A005230[k+1] := sum('A005230[j]','j'=k+1-(ceil((sqrt(8*k+1)-1)/2))..k): od: [seq(A005230[k],k=1..n)]; # UlrSchimke(AT)aol.com, Mar 16 2002

Mathematica

Module[{lst={1,1},n=2},While[n<40,AppendTo[lst,Total[ Take[lst, -Ceiling[ (Sqrt[8n+1]-1)/2]]]];n++];lst] (* Harvey P. Dale, Apr 02 2012 *)

PARI

a(n)=if(n==1,1,sum(k=1,ceil((sqrt(8*n-7)-1)/2),a(n-k))) \\ Paul D. Hanna, Aug 28 2006

PARI

v=vector(10^3);v[1]=v[2]=1;v[3]=2;v[4]=3;u=vector(#v,i,if(i>4,0,sum(j=1,i,v[j])));for(i=5,#v,m=ceil((sqrt(8*i-7)-1)/2);v[i]=u[i-1]-u[i-m-1];u[i]=u[i-1]+v[i]);u=0;v \\ Charles R Greathouse IV, Sep 19 2011

Python

from itertools import count, islice
from math import isqrt
def A005230_gen(): # generator of terms
    blist = [1]
    for n in count(1):
        yield blist[-1]
        blist.append(sum(blist[-i] for i in range(1,(isqrt(8*n)+3)//2)))
A005230_list = list(islice(A005230_gen(),30)) # Chai Wah Wu, Feb 02 2022

Formula

Partial sums give Conway-Guy sequence A005318. Cf. A066777.

2*a(n*(n+1)/2 + 1) = a(n*(n+1)/2 + 2) for n>=1; lim_{n->oo} a(n+1)/a(n) = 2. - Paul D. Hanna, Aug 28 2006

Extensions

Name corrected by Mario Szegedy, Sep 15 1996

Name revised by Ulrich Schimke (ulrschimke(AT)aol.com), Mar 16 2002