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

Author

Franklin T. Adams-Watters, Apr 26 2006

Keywords

• nonn

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

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)

Examples

			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.
		

Links

• Martin Fuller, Graph of sequences counted by A117294
• Martin Fuller, C++ program

Crossrefs

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

Programs

Racket

(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

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.