Sequences end

Before submitting this sequence to the OEIS, some help would be required : could someone compute it's last term ?

Here is how it goes :

1 2 3 4 5 6 7 8 9 20 30 22 23 24 25 26 27 28 11 33...

« Smallest available integer which doesn't include any of the digits writing it's rank in the sequence. »

Ex. : the first term of the sequence cannot be « 1 » as this « 1 » would be the same as the « 1 » which marks it's rank in the sequence. The smallest available integer is 0 (zero).

« 20 » is at rank 11 because « 20 » is the smallest avai- lable interger with no « 1 » in it.

« 30 » is at rank 12 because « 30 » is the smallest avai- lable interger with no « 1 » and no « 2 » in it.

« 22 » is at rank 13, etc.

No, sorry, bad copy/paste, it goes like this, of course :

0 1 2 3 4 5 6 7 8 9 20 30 22 23 24 25 26 27 28 11 33

Best,

It just demands how much previous 'demand' there has been in the series for all-9 numbers.

Dgates schrieb:

You forgot about 0. The final number will be where you say it is since '0' is used up, but it will contain 9 and 0 digits.

BTW, this is *very* similar to A096779 http://www.research.att.com/cgi-bin/access.cgi/as/njas/ sequences/eisA...

(only difference being that you start at 0, A096779 starts at 1)

Luc K

Point A: 123456788 is the last Rank and we can use 0 or 9 in this case. In fact, any arrangement of Rank=12345678x where x=1-8 requires the use of 0 or 9 and no other number. Call these 90numbers. The number of combinations of 12345678x is 9!*8/2=1451520. So we will need to use at least this amount of 90numbers. Point B: For Rank=12345678 we can only use 90numbers. The number of combinations of 12345678 is 8!=40320. So we will need to use at least this amount of 90numbers.

Point C For Rank=123456777 we can only use 980numbers. And for 123456888 we can only use 970numbers The number of combinations that can only use 9?0numbers is 9!/3!*8=483840. So we will need to use at least this amount of 9?0numbers. How many digits are we talking about here: Number of digits N= 2^N+8*(sum M=1 to N)[N!*2^(N-M)/M!(N-M!]>483840 or 11 digits The number of 90numbers that have up to 11 digits is about 2^12=4096 which is very small

So a good approximation would be that we need 1451520+40320 90numbers. To find the actual 90number convert this to binary number with 9=1 and we get 909909900009990000000 So this is approximately the last term.

Major error in my last post please ignore it!

The math gets laborious so hopefully I haven't goofed up here. I will only be able to find an approximate answer to the last number. Note: I shall use ~ for approximately.

Point A: 123456788 is the last Rank and we can only use 0 or 9 in this case. Also any arrangement of Rank=12345678 requires the use of 0 or 9 and no other number. Call these 90numbers. Let us find all 9 digit Ranks <=123456788 that can only use 90numbers: 112345678 with all permutations of 2-8 = 7! combinations 121345678 with all permutations of 3-8 = 6! combinations 123145678 with all permutations of 4-8 = 5! combinations .... 123456781 has no permutations = 0! combinations Total combinations when you have two 1s is 0!+1!+2!+...7!

122345678 with all permutations of 3-8=6! 123245678 with all permutations of 4-8=5! ... 123456782 has no permutations = 0! combinations Total combinations when you have two 2s is 0!+1!+2!+...6!

123345678 with all permutations of 4-8=5! ... 123456783 has no permutations = 0! combinations Total combinations when you have two 3s is 0!+1!+2!+...5! etc.

We want to find the total number of combinations for all of the above numbers, which is: 0!+1!+...7! + 0!+1!+...6!+ ... 0!+1! + 0!=6993 Point B: For Rank=12345678 we can only use 90numbers. The number of combinations of 12345678 is 8!=40320. So we will also need to use this amount of 90numbers. Combining numbers for B and C we have ~47000 Now lets figure out how many 9,0digits this requires. 90numbers are basically binary if you set 9=1. If we define 009=9 then the number of N digit base 2 numbers (which include lower digit numbers because of the 0) = 2^N so 2^N>47000 so N=16 digits Point C For Rank=12345677 we can only use 980numbers. And for 12345688 we can only use 970numbers Can we get an approximation of how many 9?0numbers there are? Suppose we approximate this with finding all Ranks<100000000 that force 9?0numbers. Ranks like AABCDEFG where A is different from B-G and A-G=1-8 give us 9?0numbers. ABCDEFG also does. Total combinations for AABCDEFG=8!*8*7/2! Total combinations for ABCDEFG=7!*8 Total number of combinations~1200000 9?0numbers are base 3. We define 009?=9?. So the number of all N digit base 3 numbers (which include lower digit numbers because of the 0) = 3^N so 3^N>1200000 or N ~ 13 digits. Comparing this to Part B's 16 digits. Thus we ignore the contribution from 9?0numbers. Point D Doing a similar calculation for 9xy0numbers shows N ~ 12 digits again ignore this contribution. Conclusion: To find the actual 90number convert 47000 to binary number and substitute 1 with 9: Last number ~9900000000000000 accurate to around first 3 digits.

Alan Sagan schrieb:

Major error in this post as well.

[Point C snipped as you discard it]

You assume that those 47000 numbers you get by enumeration can actually be used in the sequence. This is not so; many 90numbers are lost and cannot be used.

Example: Take ranks 112345678 to 112345687 to 1123456789. rank 112345678 requires a 90number, e.g. 909090. I pulled 909090 out of a hat; the number is probably incorrect, but serves as an example. rank 112345679 requires no 9, e.g. 8000000. We have skipped in this simple step the numbers 909099, 909900, 909909, 909990, 909999, 990000, ..., 999999, 21 numbers in all. rank 112345680 then calls for 9000000 since that is the smallest number

I'll repeat and summarize:

rank 112345678 -> 909090 ** (pulled out of hat) rank 112345679 -> 8000000 ## (21 90numbers wasted) rank 112345680 -> 9000000 Another 90number 'wasted'. rank 112345681 -> 9000007 rank 112345682 -> 9000009 Another 90number 'wasted'. rank 112345683 -> 9000070 rank 112345684 -> 9000077 rank 112345685 -> 9000079 rank 112345686 -> 9000090 Another 90number wasted. rank 112345687 -> 9000099 ** planned use of 90number rank 112345688 -> 9000700 rank 112345689 -> 70000000 ## (60 90numbers wasted.)

We observe that after each 'planned' 90number that you have so carefully enumerated in points A and B above, there is a rank containing a '9' which necessitates adding a digit to the sequence number.

If your above computations are correct, the final sequence number should then have at least 47000 digits!

A more thorough investigation is needed to gain a more accurate result, but it is clear that your result was still much too low.

Cheers

Michael Mendelsohn schrieb:

Hmm, how unintentionally true. I forgot that the sequence is not monotonous. Since 90numbers can be reused, your estimate is probably correct.

Sorry.

Eric Angelini schrieb:

To make up for that stupid post I made a few hours ago (I have since gotten some sleep), I am now going to attempt to compute the highest number in the sequence, which I surmise is on position 123456780.

Consider rank 102'345'678, the lowest rank that *forces* an all-9s number. I hope that 99'999'999 has already been used, so at this point I need 999'999'999.

As Alan has shown, there are 7! + 6! + 5! + 4! + 3! + 2! + 1! permutations from 102345678 to 123456780 including, 5913 in all. Every time one of those appears, the number with all 9s gets a digit more. This means the number has 8+5913=5921 digits:

the number on rank 123456780 is 10^5921 - 1.

(Were I to print it here, it would add 83 lines to this posting.)

There can be no higher number, because although there are permutations forcing single digits, there are just as many as there are for the digit 9, and they come to fruition after 9 does (i.e. there really aren't as many, because the sequence ends before we come to them), and they're smaller than 9 when they do, which means that even my hope above is unfounded, the all-9 number is still biggest, even though it shows one digit less. I take Alan to have shown that there aren't enough 2-digit numbers to be able to challenge the 1-digit numbers in size.

Final note: The numbers on the following ranks are all 90numbers, so if anyone computes the final number (rank 123456788), the others can easily be computed as well.

No need to hope, 12345678 forces 40320 90numbers. This means all 15 digit 90numbers have been used. So 99'999'999 is definitely used.

You note later on that this is a hope. Since all 15-digit 90numbers have been used, the lowest all-9 number available has at least 16 nines. But other things use up all 9 numbers. Remember the initial sequence: 0 1 2 3 4 5 6 7 8 9 20 The all-9 number 9 is already used up by Rank=10. There are many other pesky ranks that will force an all-9 numbers. Yuck.

Note: this is the MINIMUM number of digits. But easily within 1% of the real number of digits! Maybe 8+15+5921 would be better estimate.

Rank=103456789 forces all 2-numbers and is less than 123456788. So we will hit Rank=103456789 before we end the sequence at 123456788. Now we know that the number of digits for all-2 numbers greater than or equal the number digits of the all-9 numbers, because all-2 numbers are used up first. So the argument needs polishing. This is a tricky problem.