A024537 -id:A024537 - cp's OEIS frontend

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

Franklin T. Adams-Watters, Apr 26 2006

nonn

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 0Does X have a distribution for large n and approximate c? Can this be used to work out the growth rate of a(n)? (End)

			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.

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

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

(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

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

A278476 a(n) = floor((1 + sqrt(2))^3*a(n-1)) for n>0, a(0) = 1.

Original entry on oeis.org

1, 14, 196, 2757, 38793, 545858, 7680804, 108077113, 1520760385, 21398722502, 301102875412, 4236838978269, 59616848571177, 838872718974746, 11803834914217620, 166092561518021425, 2337099696166517569, 32885488307849267390, 462733936006056261028

Offset: 0

Ilya Gutkovskiy, Nov 23 2016

In general, the ordinary generating function for the recurrence relation b(n) = floor((1 + sqrt(2))^k*b(n - 1)) with n>0 and b(0) = 1, is (1 - x)/(1 - round((1 + sqrt(2))^k)*x + x^2) if k is nonzero even, and (1 - x - x^2)/((1 - x)*(1 - round((1 + sqrt(2))^k)*x - x^2)) if k is odd or k = 0.

G. C. Greubel, Table of n, a(n) for n = 0..869
Index entries for linear recurrences with constant coefficients, signature (15,-13,-1).

Cf. A014176.

Cf. similar sequences with recurrence relation b(n) = floor((1 + sqrt(2))^k*b(n-1)) for n>0, b(0) = 1: A024537 (k = 1), A001653 (k = 2), this sequence (k = 3), A077420 (k = 4), A097733 (k = 6).

m:=25; R:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x-x^2)/((1-x)*(1-14*x-x^2)))); // G. C. Greubel, Oct 10 2018

seq(coeff(series((1-x-x^2)/((1-x)*(1-14*x-x^2)),x,n+1), x, n), n = 0 .. 20); # Muniru A Asiru, Oct 11 2018

RecurrenceTable[{a[0] == 1, a[n] == Floor[(1 + Sqrt[2])^3 a[n - 1]]}, a, {n, 18}]
LinearRecurrence[{15, -13, -1}, {1, 14, 196}, 19]
CoefficientList[Series[(1-x-x^2)/((1-x)*(1-14*x-x^2)), {x,0,50}], x] (* G. C. Greubel, Oct 10 2018 *)

Vec((1 - x - x^2)/((1 - x)*(1 - 14*x - x^2)) + O(x^50)) \\ G. C. Greubel, Nov 24 2016

G.f.: (1 - x - x^2)/((1 - x)*(1 - 14*x - x^2)).
a(n) = 15*a(n-1) - 13*a(n-2) - a(n-3).
a(n) = ((65 - 52*sqrt(2))*(7 - 5*sqrt(2))^n + 13*(5 + 4*sqrt(2))*(7 + 5*sqrt(2))^n + 10)/140.

Previous Showing 21-22 of 22 results.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Racket

Extensions

A278476 a(n) = floor((1 + sqrt(2))^3*a(n-1)) for n>0, a(0) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula