A117294 Number of sequences of length n starting with 1,2 which satisfy a recurrence a(k+1) = floor(c*a(k)) for some constant c.

1, 2, 5, 14, 37, 102, 279, 756, 2070, 5609, 15198, 41530, 114049, 315447, 876513, 2446326, 6861432, 19315953, 54556553, 154591186, 439307113, 1251678183, 3574777087, 10231666185, 29343549576, 84309936418, 242651784699, 699476361863, 2019289119525, 5837355573611, 16896103820563, 48963682959055, 142051622347551

Offset

2,2

Comments

It appears that a(n+1)/a(n) may be converging slowly to 3, but even that it converges is not obvious.

From Martin Fuller, Apr 05 2025: (Start)

Each finite sequence corresponds to a range of c, e.g. (1,2,4,9) has c in [9/4,5/2).

Let x=(maximum element)*(range width of c), e.g. x(1,2,4,9)=9*(5/2 - 9/4)=9/4.

Then the number of extensions of this sequence in a(n+1) is either floor(x)+1 or ceil(x)+1. Non-rigorously, the expected number is x+1.

Also x is bounded 0<x<=c for all finite sequences with the same c.

Does X have a distribution for large n and approximate c? Can this be used to work out the growth rate of a(n)? (End)

Links

Table of n, a(n) for n=2..34.

Martin Fuller, Graph of sequences counted by A117294

Martin Fuller, C++ program

Example

a(4) = 5: length 4 sequences are 1,2,4,8; 1,2,4,9; 1,2,5,12; 1,2,5,13; and 1,2,5,14.

Prog

(Scheme) (define (A117294 n) (local ((define (get-ratios seq add?) (cond [(empty? (rest seq)) empty] [else (cons (/ (cond [add? (add1 (first seq))] [else (first seq)]) (second seq)) (get-ratios (rest seq) add?))])) (define (extend-one seq) (local ((define startnext (floor (* (apply max (get-ratios seq false)) (first seq)))) (define endnext (ceiling (* (apply min (get-ratios seq true )) (first seq)))) (define ltodo (build-list (- endnext startnext) (lambda (n) (cons (+ startnext n) seq))))) (cond [(>= (length seq) (sub1 n)) (length ltodo)] [else (apply + (map extend-one ltodo))])))) (extend-one (list 2 1)))) ;; Joshua Zucker, Jun 05 2006

Crossrefs

Some (infinite) examples of such sequences: A000079, A007051, A076883, A001519, A024537, A024576, A057960.

Sequence in context: A077938 A077987 A143141 * A148306 A148307 A148308

Adjacent sequences: A117291 A117292 A117293 * A117295 A117296 A117297

Keyword

nonn

Author

Franklin T. Adams-Watters, Apr 26 2006

Extensions

More terms from Joshua Zucker, Jun 05 2006

Comment edited by Franklin T. Adams-Watters, May 14 2010

Ambiguous terms a(0), a(1) removed by Max Alekseyev, Jan 18 2012

a(21)-a(24) from Jinyuan Wang, Mar 20 2025

a(25)-a(34) from Martin Fuller, Apr 05 2025

Status

approved