A034587 Fibonacci iteration starting with (1, a(n)) leads to a "nine digits anagram".

718, 1790, 1993, 2061, 2259, 3888, 3960, 4004, 4396, 5093, 5832, 7031, 7310, 7712, 8039, 8955, 9236, 11598, 11742, 12312, 13295, 15095, 15432, 16044, 16355, 16472, 18109, 18559, 19144, 19950, 19968, 20116, 20180, 20494, 21170, 21376, 21998

Offset: 1

Author

Patrick De Geest, Oct 15 1998

Keywords

• nonn
• base
• fini

Comments

By "nine digits anagram" the author means a number whose digits are a permutation of {1, ..., 9}. These are more commonly known as restricted zeroless pandigital numbers and form the first 9! terms of A050289.

The largest term is a(750767) = 987654320.

More generally, the last N = 9! - 158323 = 204557 (> 56% of 9!) terms are given as A050289(k)-1 with indices k = 9!-N+1, ..., 9!. Indeed, a number > (987654321-1)/2 = 493827160 is a term if and only if it equals a "9-digit anagram" minus 1, since all results beyond the first iteration (1 + n = n+1) will be too large. Since 493827165 = A050289(158324) > 493827160, starting with a(546211) = 493827164 the terms are given by A050289(158324 .. 9!) - 1, for a total of 546211 + N - 1 = 750767 terms. (The term 493827164 is preceded by 493827160 (which yields 987654321 but is not in A050289 - 1) and 493827155 = A050289(158323) - 1.) - M. F. Hasler, Jan 07 2020

The ratio between consecutive terms in a Fibonacci sequence x(n+1) = x(n) + x(n-1) tends quickly to the golden ratio Phi = (sqrt(5)+1)/2 = A001622. We can tell whether a starting value N is in this sequence or not from the terms between 123456789 and 987654321 ~ 1e9. From N*Phi^k = 1e9 we get k = log(1e9/N)/log(Phi) ~ 43 - 2*log(N) for the maximum (and 3 less for the minimum) number of required iterations. - M. F. Hasler, Jan 06 2020

Examples

			Denote by F(a,b) the Fibonacci-type sequence x(n+1) = x(n) + x(n-1) starting with x(0) = a, x(1) = b.
Then F(1,21998) = (1, 21998, 21999, 43997, 65996, 109993, 175989, 285982, 461971, 747953, 1209924, 1957877, 3167801, 5125678, 8293479, 13419157, 21712636, 35131793, 56844429, 91976222, 148820651, 240796873, 389617524, ...) where a nine-digits anagram has been reached.
The growth is roughly linear in three parts, with a slope of 700 up to a(292967) = 206993812, then an average slope of 1130 before it rises to (9.87e8 - 4.94e8)/2.05e5 ~ 2400 for 546211 <= n <= 750767 (cf. formula & comments): a(100) = 71960, a(200) = 149540, a(500) = 351868, a(1000) = 649921, a(2000) = 1400539, a(5000) = 3209798, a(10^4) = 6595301, a(2e4) = 13351498, a(5e4) = 32441506, a(10^5) = 67090523, a(2e5) = 134759627, a(3e5) = 214973567, a(4e5) = 327136594, a(5e5) = 439256717. - _M. F. Hasler_, Jan 07 2020
		

Links

• M. F. Hasler, Table of n, a(n) for n = 1..10000, Jan 06 2020. (Full list of 750767 terms is available on request.)
• Patrick De Geest, Nine Digits Digressions
• M. F. Hasler, Graph of A034587, n = 1..750767 (full sequence), Jan 10 2020
• M. F. Hasler, Slope of A034587, averaged over n +- 10 sqrt(n), Jan 10 2020

Crossrefs

Subsequences: A034588 (primes), A034589 (lucky numbers), A034306 (palindromes).

Programs

PARI

A034587=select( {is_A034587(n,s=1,L=[1..9])=while( 123456789 > n=s+s=n,); n<1e9 && until( 987654321 < n=s+s=n, Set(digits(n))==L&&return(n))}, [1..22222]) \\ Function is_A034587 returns the 9-digit anagram if one is reached; null == false == 0 else.
nxt_A034587(n)={until(is_A034587(n+=1),);n} \\ Returns next larger term
A034587(n)={if(n>546210, A050289(n-387887)-1, #A034587>=n, A034587[n], A034587=concat( A034587, vector(n-#A034587,i, n=nxt_A034587(if(i>1,n,A034587[#A034587])))); n)} \\ Uses the two functions above. Could use Vecsmall(...) in definition of A034587 and vectorsmall in A034587(n) to reduce memory.
\\ M. F. Hasler, Jan 06 2020 and Jan 07 2020

Python

def ok(n):
    f, g = n, n+1
    while g < 10**9:
        if g > 123456788 and "".join(sorted(str(g))) == "123456789":
            return True
        f, g = g, f+g
    return False
print([k for k in range(10**4) if ok(k)]) # Michael S. Branicky, Feb 18 2024

Formula

a(n) = A050289(m) with n = 387887 + m for 158324 <= m <= 9! or 546211 <= n <= 750767 = total number of terms in this sequence. - M. F. Hasler, Jan 07 2020

Extensions

Edited and offset changed to 1 by M. F. Hasler, Jan 06 2020

Results confirmed by Giovanni Resta, Jan 07 2020