Non Recursions

These are the sequences that pass recursion tests, but from their definitions it is not clear if they are recursions. I added comments for the sequences that I know not to be recursions. See the main page Recursive Sequences.

• Interesting sequences - I would like to know if they are recurrences or not.
• a(n) = d * a(n-1) - a(n-2).
• a(n) = d * a(n-1) + d * a(n-2).
• a(n) = d * a(n-1) + a(n-2).
• a(n) = a(n-1) + a(n-2).
• a(n) = d * a(n-1). Geometric progressions.
• a(n) = a(n-1) + d. Arithmetic progressions.
• a(n) = a(n-1). Constants.
• Comments.

This page is synchronized with OEIS in January 2007. Sequences in OEIS might start with a different index.

Interesting Sequences.

Sequences:

• A123464 a(n) = 2*a(n-1), a(0) = 1.
  Number of threshold perfect graphs on n nodes.
• A070300 a(n) = a(n-1) + 3, a(0) = 4.
  Minimal number of 0's in a 2n X 2n (0,1) matrix that contains no n X n submatrix of 1's.
• A085805 a(n) = a(n-1) + 16, a(0) = 4.
  Numbers n such that the permanent of the character table of the dihedral group D_n is not zero.
• A114142 a(n) = a(n-1) + 1, a(0) = 2.
  Possible sums of the final scores of completed Chicago Bears football games.
• A114143 a(n) = a(n-1) + 1, a(0) = 4.
  The possible sums of the final scores of completed Chicago Bears football games where both teams score.
• A118759 a(n) = a(n-1) + 1, a(0) = 0.
  A118757(A118757(n)).
• A118760 a(n) = a(n-1) + 1, a(0) = 0.
  A118758(A118758(n)).

a(n) = d * a(n-1) - a(n-2).

Sequences:

• a(n) = 2a(n-1) - a(n-2). For d = 2 see arithmetic progressions.
• A011783 a(n) = 3*a(n-1) - a(n-2), a(0) = 1, a(1) = 1.
  Duplicate of A001519. (dead sequence)
• A077461 a(n) = 6*a(n-1) - a(n-2), a(0) = 2, a(1) = 14.
  Same as A077444. (dead sequence)
• A087096 a(n) = 4*a(n-1) - a(n-2), a(0) = 1, a(1) = 2.
  Same as A001075. (dead sequence)

a(n) = d * a(n-1) + d * a(n-2).

Sequences:

• a(n) = a(n-1) + a(n-2). For d = 1 see a(n) = a(n-1) + a(n-2).
• A085481 a(n) = 3*a(n-1) + 3*a(n-2), a(0) = 1, a(1) = 3.
  Same as A030195. (dead sequence)

a(n) = a(n-1) + a(n-2).

Sequences:

• A077373 a(n) = a(n-1)+a(n-2), a(0) = 0, a(1) = 1.
  Fibonacci numbers whose external digits as well as internal digits form a Fibonacci number.
  Non-recursion - subsequence of Fibonacci numbers.

a(n) = d * a(n-1) + a(n-2).

Sequences:

• a(n) = a(n-1) + a(n-2). For d = 1 see a(n) = a(n-1) + a(n-2).
• A048624 a(n) = 2*a(n-1)+a(n-2), a(0) = 2, a(1) = 5.
  Essentially a duplicate of A000129. (dead sequence)
• A084133 a(n) = 6*a(n-1)+a(n-2), a(0) = 1, a(1) = 3.
  Duplicate of A005667. (dead sequence)

a(n) = d * a(n-1). Geometric progressions.

Sequences:

• a(n) = a(n-1). For d = 1 see constants.
• A025489 a(n) = 2*a(n-1), a(0) = 2.
  Numbers on backgammon doubling cube.
  Finite sequence - non recursive.
• A060365 a(n) = 1000*a(n-1), a(0) = 1.
  Multiples of one million which are described by single words in American English.
  Finite sequence - non recursive.
• A060366 a(n) = 1000*a(n-1), a(0) = 1.
  Multiples of one million which are described by single words in British English.
  Finite sequence - non recursive.
• A067482 a(n) = 1024*a(n-1), a(0) = 4.
  Powers of 4 with initial digit 4.
• A067484 a(n) = 10077696*a(n-1), a(0) = 6.
  Powers of 6 with initial digit 6.
• A121499 a(n) = 841*a(n-1), a(0) = 1.
  Denominators of partial alternating sums of Catalan numbers scaled by powers of 1/(29^2) = 1/841.
  Non recursive. Comment by Max Alekseyev: The recurrent formula fails as soon as C(n) is divisible by 29. First time it happens for n=15.
• A123464 a(n) = 2*a(n-1), a(0) = 1.
  Number of threshold perfect graphs on n nodes.
• A125581 a(n) = 11*a(n-1), a(0) = 77.
  Numbers n such that n does not divide the denominator of the n-th harmonic number nor the denominator of the n-th alternating harmonic number.
  Non-recursive. Comment by Max Alekseyev: While A125581 indeed contains the geometric progression 7*11ⁿ as a subsequence, it also contains other geometric progressions such as: 506*1093ⁿ, 1092*1093ⁿ, 1755*3511ⁿ, 3510*3511ⁿ, and 4896*5557ⁿ.

a(n) = a(n-1) + d. Arithmetic progressions.

Sequences:

• a(n) = a(n-1). For d = 0 see constants.
• A004924 a(n) = a(n-1) + 76, a(0) = 0.
  Floor of n*tau^9.
• A004926 a(n) = a(n-1) + 199, a(0) = 0.
  Floor of n*tau^11.
• A004928 a(n) = a(n-1) + 521, a(0) = 0.
  Floor of n*tau^13.
• A004930 a(n) = a(n-1) + 1364, a(0) = 0.
  Floor of n*tau^15.
• A004932 a(n) = a(n-1) + 3571, a(0) = 0.
  Floor of n*tau^17.
• A004934 a(n) = a(n-1) + 9349, a(0) = 0.
  Floor of n*tau^19.
• A004944 a(n) = a(n-1) + 76, a(0) = 0.
  Nearest integer to n*tau^9.
• A004945 a(n) = a(n-1) + 123, a(0) = 0.
  Nearest integer to n*tau^10.
• A004946 a(n) = a(n-1) + 199, a(0) = 0.
  Nearest integer to n*tau^11.
• A004947 a(n) = a(n-1) + 322, a(0) = 0.
  Nearest integer to n*tau^12.
• A004948 a(n) = a(n-1) + 521, a(0) = 0.
  Nearest integer to n*tau^13.
• A004949 a(n) = a(n-1) + 843, a(0) = 0.
  Nearest integer to n*tau^14.
• A004950 a(n) = a(n-1) + 1364, a(0) = 0.
  Nearest integer to n*tau^15.
• A004951 a(n) = a(n-1) + 2207, a(0) = 0.
  Nearest integer to n*tau^16.
• A004952 a(n) = a(n-1) + 3571, a(0) = 0.
  Nearest integer to n*tau^17.
• A004953 a(n) = a(n-1) + 5778, a(0) = 0.
  Nearest integer to n*tau^18.
• A004954 a(n) = a(n-1) + 9349, a(0) = 0.
  Nearest integer to n*tau^19.
• A004955 a(n) = a(n-1) + 15127, a(0) = 0.
  Nearest integer to n*tau^20.
• A004963 a(n) = a(n-1) + 47, a(0) = 0.
  Ceiling of n*tau^8.
• A004965 a(n) = a(n-1) + 123, a(0) = 0.
  Ceiling of n*tau^10.
• A004967 a(n) = a(n-1) + 322, a(0) = 0.
  Ceiling of n*tau^12.
• A004969 a(n) = a(n-1) + 843, a(0) = 0.
  Ceiling of n*tau^14.
• A004971 a(n) = a(n-1) + 2207, a(0) = 0.
  Ceiling of n*tau^16.
• A004973 a(n) = a(n-1) + 5778, a(0) = 0.
  Ceiling of n*tau^18.
• A004975 a(n) = a(n-1) + 15127, a(0) = 0.
  Ceiling of n*tau^20.
• A008553 a(n) = a(n-1) + 1, a(0) = 20.
  Numbers that contain the letter `y'.
  Non recursive.
• A017149 a(n) = a(n-1) + 8, a(0) = 7.
  Same as A004771. (dead sequence)
• A031193 a(n) = a(n-1) + 3, a(0) = 3.
  Numbers having period-22 5-digitized sequences.
  Non recursive.
• A032614 a(n) = a(n-1) + 101, a(0) = 110.
  Concatenation of n and n + 9 or {n,n+9}.
  Non recursive.
• A033168 a(n) = a(n-1) + 210, a(0) = 199.
  Longest arithmetic progression of primes with difference 210 and minimal initial term.
  Finite sequence - non recursive.
• A033290 a(n) = a(n-1) + 210, a(0) = 100996972469714247637786655587969840329509324689190041803603417758904341703348882159067229719.
  Ten consecutive primes in arithmetic progression.
  Finite sequence - non recursive.
• A044138 a(n) = a(n-1) + 49, a(0) = 49.
  Numbers n such that string 0,0 occurs in the base 7 representation of n but not of n-1.
  Non recursive. See Comment.
• A044179 a(n) = a(n-1) + 49, a(0) = 41.
  Numbers n such that string 5,6 occurs in the base 7 representation of n but not of n-1.
  Non recursive. See Comment.
• A044187 a(n) = a(n-1) + 64, a(0) = 64.
  Numbers n such that string 0,0 occurs in the base 8 representation of n but not of n-1.
  Non recursive. See Comment.
• A044242 a(n) = a(n-1) + 64, a(0) = 55.
  Numbers n such that string 6,7 occurs in the base 8 representation of n but not of n-1.
  Non recursive. See Comment.
• A044251 a(n) = a(n-1) + 81, a(0) = 81.
  Numbers n such that string 0,0 occurs in the base 9 representation of n but not of n-1.
  Non recursive. See Comment.
• A044322 a(n) = a(n-1) + 81, a(0) = 71.
  Numbers n such that string 7,8 occurs in the base 9 representation of n but not of n-1.
  Non recursive. See Comment.
• A044332 a(n) = a(n-1) + 100, a(0) = 100.
  Numbers n such that string 0,0 occurs in the base 10 representation of n but not of n-1.
  Non recursive. See Comment.
• A044421 a(n) = a(n-1) + 100, a(0) = 89.
  Numbers n such that string 8,9 occurs in the base 10 representation of n but not of n-1.
  Non recursive. See Comment.
• A044567 a(n) = a(n-1) + 49, a(0) = 48.
  Numbers n such that string 6,6 occurs in the base 7 representation of n but not of n+1.
  Non recursive. See Comment.
• A044631 a(n) = a(n-1) + 64, a(0) = 63.
  Numbers n such that string 7,7 occurs in the base 8 representation of n but not of n+1.
  Non recursive. See Comment.
• A044712 a(n) = a(n-1) + 81, a(0) = 80.
  Numbers n such that string 8,8 occurs in the base 9 representation of n but not of n+1.
  Non recursive. See Comment.
• A044812 a(n) = a(n-1) + 100, a(0) = 99.
  Numbers n such that string 9,9 occurs in the base 10 representation of n but not of n+1.
  Non recursive. See Comment.
• A046050 a(n) = a(n-1) + 80, a(0) = 79.
  Sum of 19 but no fewer nonzero fourth powers.
  Finite sequence - non recursive.
• A047738 a(n) = a(n-1) + 1, a(0) = 179210312.
  Earliest sequence of 4 consecutive economical numbers.
  Finite sequence - non recursive.
• A050518 a(n) = a(n-1) + 583200, a(0) = 583200.
  Arithmetic progression of at least 6 terms having the same value of phi start at these numbers.
  Non-recursive. Comment by Max Alekseyev: a(3888)=3889*583200 does NOT belong to A050518.
• A050519 a(n) = a(n-1) + 30, a(0) = 30.
  Increments of arithmetic progression of at least 6 terms having the same value of phi in A050518.
• A058908 a(n) = a(n-1) + 9876543210, a(0) = 5077.
  Six prime numbers in arithmetical progression with a common difference of 9876543210.
  Finite sequence - non recursive.
• A059558 a(n) = a(n-1) + 4, a(0) = 4.
  Beatty sequence for 1+1/gamma^2.
  Non recursive. Comment by Max Alekseyev: a first counterexample to recurrence is a(715)=2861.
• A069782 a(n) = a(n-1) + 1, a(0) = 1.
  Numbers n such that g[n] := GCD[d[n^3],d[n]] = 2^w for some w. The first missing integer is 432 (See in A069781).
  Non recursive.
• A070300 a(n) = a(n-1) + 3, a(0) = 4.
  Minimal number of 0's in a 2n X 2n (0,1) matrix that contains no n X n submatrix of 1's.
• A074337 a(n) = a(n-1) + 9922782870, a(0) = 107928278317.
  18 primes in arithmetic progression.
  Finite sequence - non recursive.
• A081734 a(n) = a(n-1) + 30, a(0) = 121174811.
  First and smallest sequence of 6 consecutive primes in arithmetic progression.
  Finite sequence - non recursive.
• A082221 a(n) = a(n-1) + 6, a(0) = 1.
  In the following square array numbers (not occurring earlier) are entered like this a(1,1),a(1,2),a(2,1),a(3,1),a(2,2),a(1,3),a(1,4),a(2,3),a(3,2),a(4,1),a(5,1),a(4,2),... such that every n-th partial sum of a row or a column is a multiple of n. 1 3 2 10 19 25... 5 7 12 16 15... 6 8 13 37... 4 14 18... 9 23... 11... ... Sequence contains the main diagonal.
  Non recursive - more terms calculated by Max Alekseyev.
• A082249 a(n) = a(n-1) + 7070707070707, a(0) = 22212019181716.
  Reverse concatenation of 7 numbers that are multiples of 7.
  Non recursive. Comment by Max Alekseyev: The next term of A082249 is 108107106105104103102 and it does NOT satisfy the recurrent formula.
• A082946 a(n) = a(n-1) + 101, a(0) = 111.
  Palindromes satisfying A082945.
  Non recursive. Comment by Max Alekseyev: if it were a recursive sequence then the next (currently unlisted) term would be 919+101=1020 which is not a palindrome.
• A085805 a(n) = a(n-1) + 16, a(0) = 4.
  Numbers n such that the permanent of the character table of the dihedral group D_n is not zero.
• A088475 a(n) = a(n-1) + 1, a(0) = 10.
  Numbers n such that dismal sum of prime divisors of n is ≥ n.
  Non-recursive.
• A088480 a(n) = a(n-1) + 1, a(0) = 1.
  Numbers n such that dismal product of prime divisors of n is ≥ n.
  Non-recursive. Complement of A088477
• A096582 a(n) = a(n-1) - 1, a(0) = 100.
  From the "100 Green Bottles" song.
  Finite sequence - non recursive.
• A103303 a(n) = a(n-1) + 1, a(0) = 0.
  Complete list of digits used in the counting numbers (in base 10). Also known as the "arabic numerals".
  Finite sequence - non recursive.
• A104340 a(n) = a(n-1) + 11, a(0) = 12.
  Numbers n such that (digital reversal of n) - n = 9.
  Finite sequence - non recursive.
• A104341 a(n) = a(n-1) + 11, a(0) = 10.
  Numbers n such that n -(digital reversal of n) = 9.
  Finite sequence - non recursive.
• A104342 a(n) = a(n-1) + 11, a(0) = 13.
  Numbers n such that (digital reversal of n) - n = 18.
  Finite sequence - non recursive.
• A107843 a(n) = a(n-1) - 2, a(0) = 201.
  Number of iterations of McCarthy 91 Function until it terminates.
  Non recursive.
• A109065 a(n) = a(n-1) - 1, a(0) = 12.
  Numerator of the fraction due in month n of the total interest for a one-year installment loan based on the Rule of 78s (Each denominator is 78).
  Finite sequence - non recursive.
• A109632 a(n) = a(n-1) + 300, a(0) = 200.
  In the game of bridge, a(n) is the penalty for going down n tricks in a vulnerable, doubled contract.
  Finite sequence - non recursive.
• A112821 a(n) = a(n-1) + 1, a(0) = 343.
  Numbers n such that 19*LCM(1,2,3,...,n) equals the denominator of the n-th harmonic number H(n).
  Non recursive. Comment by Max Alekseyev: 361 does not belong to A112821.
• A114142 a(n) = a(n-1) + 1, a(0) = 2.
  Possible sums of the final scores of completed Chicago Bears football games.
• A114143 a(n) = a(n-1) + 1, a(0) = 4.
  The possible sums of the final scores of completed Chicago Bears football games where both teams score.
• A115020 a(n) = a(n-1) - 7, a(0) = 100.
  Count backwards from 100 in steps of 7.
  Finite sequence - non recursive.
• A115536 a(n) = a(n-1) + 9434, a(0) = 160378.
  Numbers n such that the square of n is the concatenation of two numbers m and 4*m.
• A115548 a(n) = a(n-1) + 30434782608695652173913043478260869565217391304347826087, a(0) = 91304347826086956521739130434782608695652173913043478261.
  Numbers n such that the square of n is the concatenation of two numbers m and 7*m.
• A118759 a(n) = a(n-1) + 1, a(0) = 0.
  A118757(A118757(n)).
• A118760 a(n) = a(n-1) + 1, a(0) = 0.
  A118758(A118758(n)).
• A120420 a(n) = a(n-1) + 1, a(0) = 2.
  Numbers n such that n! is highly composite (in the sense of A002182).
  Non recursive.
• A121377 a(n) = a(n-1) + 1, a(0) = 48.
  ASCII codes for decimal digits.
  Finite sequence - non recursive.
• A121378 a(n) = a(n-1) + 1, a(0) = 240.
  EBCDIC codes for decimal digits.
  Finite sequence - non recursive.

a(n) = a(n-1). Constants.

Sequences:

• A058445 a(n) = 2236081408416666.
  Numbers n such that n^2 contains only digits {0,5,6}, not ending with zero.
  Contains only one number - non recursive.
• A058446 a(n) = 5000060065066660656065066555556.
  Squares composed of digits {0,5,6}, not ending with zero.
  Contains only one number - non recursive.
• A072288 a(n) = 316912650057057350374175801344000001.
  Smallest prime factor of Googolplex + n which exceeds 16.
  Contains only one number - non recursive.
• A076337 a(n) = 509203.
  Riesel numbers: n such that for all k ≥ 1 the numbers n*2^k - 1 are composite.
  Contains only one number - non recursive.
• A082710 a(n) = 10907.
  Plateau and depression primes of the form (10^a(n)-1)/9+6*(10^[ a(n)-1 ]+1) or (64*10^[ a(n)-1 ]+53)/9.
  Contains only one number - non recursive.
• A115453 a(n) = 1414213562373095048801688724209698078569671875376948073.
  Numbers n such that the first n digits of Sqrt[2] form a prime.
  Contains only one number - non recursive.
• A118329 a(n) = 9159655941772190150546035149323841107741493742816721.
  Catalan-primes: primes formed from the concatenation of initial decimal digits of Catalan's constant.
  Contains only one number - non recursive.

Comments.

• The following comment was sent to me by Max Alekseyev. All sequences of the type "Numbers n such that string x,y occurs in the base b representation of n but not of n-1" are not recursive.
  • If x=y=0 then the first deviation is b⁴+b²=b²*(b²+1).
  • If x=y is non-zero then the first deviation is x*(b²+b+1).
  • If x and y are distinct then the first deviation is x*b³+y*b²+x*b+y=(x*b+y)*(b²+1).

• Back to Tanya Khovanova's welcome page

• Contact me: Tanya Khovanova

  tanyakh@yahoo.com

Last revised March 2007