//

**Edited by Vidar son of Odin, 04 April 2014 - 06:51 AM.**

Started by Mr. Lawliet, Apr 02 2014 10:05 AM

15 replies to this topic

Posted 02 April 2014 - 11:00 AM

How did you found this string? It's an excercise from a book or something? Or you know a crazy man how repeats them? If it's the latter, don't us them to win the lottery!

Anyway, if it's really supposed to be a sequence with some logic it also depends if it's a learning excercice or a lateral thinking excercise.

The only points I can see are:

- Every number contains a 9
- After a number composed of all 9's a new digit is added
- For a certain number of digit, the valid values for each digits are 1 less than the valid values (1 digit > 9, 2 digits > 8 and 9, 3 digits > 7, 8 and 9).
- It looks like if a number starts with 9, the next number has the first 2 digits swapped.
- I have no idea of more rules, but clearly there are more things going on (why is it 899 the next number? no idea)

So, for the next number I'd guess is something like 6789 and the next one maybe 6798, but it's just a guess, there's no function or arlgorithm I can think of.

Posted 02 April 2014 - 11:25 AM

Found it, thanks to DiegoSLTS observations...

Every time a new digit is added.

First you start with a nine, you can't swap anything there. Then you add a second digit and you allow numbers 8 and 9. Then you have three possibilities if every number should include at least one 9: 98, 89 and 99. After that you add another digit. The numbers allowed are 7, 8 and 9 like DiegoSLTS said. All numbers should again not have two times the same number except for the nine.

9

89 98 99

789 798 879 897 899 978 987 989 998 999

As you can see the numbers are grouped in terms of number of digits. The first number starts with the lowest digit first. The last number contains only nines. Aside from that I don't see the exact order inside a "digit group". But it looks like the order "prefers" lower digits first. Is this the pattern or is there also a pattern inside the groups?

**Edited by ProtectedMode, 02 April 2014 - 11:26 AM.**

Posted 02 April 2014 - 11:35 AM

Those are the numbers whose histograms of digits are weakly increasing.

perl -e 'NUMBER: for $n (1..1000) {%c=(); for $d (split "",$n){$c{$d}++}; for $d (1..9) {next NUMBER if $c{$d} < $c{$d-1}} print "$n\n"}'

Could you maybe provide the output too for people who don't have Perl installed?

Posted 02 April 2014 - 11:36 AM

Outer loop seed = {9, 89, 789, 6789, ... 123456789, MAYBE 0123456789 }

Inner loop: Take the digits you have available (for example with 789, you have the digits 7,8, and 9 to work with) and find the next higher integer with the same number of digits which uses only the digits you have available. Terminate the inner loop when all digits are 9.

Your method would produce 877, but that wasn't in the list.

Posted 02 April 2014 - 11:37 AM

Those are the numbers whose histograms of digits are weakly increasing.

perl -e 'NUMBER: for $n (1..1000) {%c=(); for $d (split "",$n){$c{$d}++}; for $d (1..9) {next NUMBER if $c{$d} < $c{$d-1}} print "$n\n"}'Could you maybe provide the output too for people who don't have Perl installed?

9 89 98 99 789 798 879 897 899 978 987 989 998 999

If you loop till 10000, you get

9 89 98 99 789 798 879 897 899 978 987 989 998 999 6789 6798 6879 6897 6978 6987 7689 7698 7869 7896 7899 7968 7986 7989 7998 8679 8697 8769 8796 8799 8899 8967 8976 8979 8989 8997 8998 8999 9678 9687 9768 9786 9789 9798 9867 9876 9879 9889 9897 9898 9899 9978 9987 9988 9989 9998 9999

Posted 02 April 2014 - 11:39 AM

Found it, thanks to DiegoSLTS observations...

Every time a new digit is added.

First you start with a nine, you can't swap anything there. Then you add a second digit and you allow numbers 8 and 9. Then you have three possibilities if every number should include at least one 9: 98, 89 and 99. After that you add another digit. The numbers allowed are 7, 8 and 9 like DiegoSLTS said. All numbers should again not have two times the same number except for the nine.

9

89 98 99

789 798 879 897 899 978 987 989 998 999

As you can see the numbers are grouped in terms of number of digits. The first number starts with the lowest digit first. The last number contains only nines. Aside from that I don't see the exact order inside a "digit group". But it looks like the order "prefers" lower digits first. Is this the pattern or is there also a pattern inside the groups?

Your method would produce 799, but that wasn't in the list.

Posted 02 April 2014 - 11:44 AM

Your method would produce 877, but that wasn't in the list.All numbers should again not have two times the same number except for the nine.

If you quote from unrelated posts, you'll confuse everybody. In the post where I object to your method, I complain about 799. I was complaining about 877 for Nypyren's method.

Posted 03 April 2014 - 05:48 AM

Alvaro, I still can't really code a program to generate this numbers in c++.

Here it is in C++:

#include <iostream> bool check_histogram_of_digits_is_weakly_increasing(unsigned long x) { int histogram[10] = {0}; do { histogram[x % 10]++; x /= 10; } while (x > 0); for (int i=0; i<9; ++i) { if (histogram[i] > histogram[i+1]) return false; } return true; } int main() { for (int i=1; i<10000; ++i) { if (check_histogram_of_digits_is_weakly_increasing(i)) std::cout << i << '\n'; } }

Why your method produce 9988?

Because its histogram of digits is (0,0,0,0,0,0,0,0,2,2), which is weakly increasing.

**Edited by Álvaro, 03 April 2014 - 05:51 AM.**

Posted 03 April 2014 - 06:57 AM

Thank you very much Alvaro. I don't really understand what " histogram of digits is weakly increasing" means but I found an article about histograms on wikipedia. I will read it and hopefully understand it. Thank you.

**Edited by Bratie Fanut, 03 April 2014 - 07:01 AM.**

*"Don't gain the world and lose your soul. Wisdom is better than silver or gold."* - Bob Marley

Posted 03 April 2014 - 07:44 AM

Thank you very much Alvaro. I don't really understand what " histogram of digits is weakly increasing" means but I found an article about histograms on wikipedia. I will read it and hopefully understand it. Thank you.

"Histogram" is just a fancy name for "one counter for each possible value". I think my C++ code should be fairly easy to read, but I'll give you a couple of examples in English.

Let's see why the number 799 is not in the list. Let's count how many times each digit appear in 799: "0" appears 0 times, "1" appears 0 times, ..., "7" appears 1 time, "8" appears 0 times and "9" appears 2 times. Putting all ten counters in a row, it's (0,0,0,0,0,0,0,1,0,2), and this is what I am calling the "histogram". As you see there are more "7"s than "8"s, so this sequence is not weakly increasing.

Let's now see why the number 989 is in the list. The histogram is (0,0,0,0,0,0,0,0,1,2). This is weakly increasing (i.e., every number is either the same as the one before it or larger).

Posted 03 April 2014 - 10:36 AM

Thank you very much Alvaro. I don't really understand what " histogram of digits is weakly increasing" means but I found an article about histograms on wikipedia. I will read it and hopefully understand it. Thank you.

"Histogram" is just a fancy name for "one counter for each possible value". I think my C++ code should be fairly easy to read, but I'll give you a couple of examples in English.

Let's see why the number 799 is not in the list. Let's count how many times each digit appear in 799: "0" appears 0 times, "1" appears 0 times, ..., "7" appears 1 time, "8" appears 0 times and "9" appears 2 times. Putting all ten counters in a row, it's (0,0,0,0,0,0,0,1,0,2), and this is what I am calling the "histogram". As you see there are more "7"s than "8"s, so this sequence is not weakly increasing.

Let's now see why the number 989 is in the list. The histogram is (0,0,0,0,0,0,0,0,1,2). This is weakly increasing (i.e., every number is either the same as the one before it or larger).

Oohh.. I understand now And understand why on wikipedia on histogram article was a lot of graphics and statistics Thank you very much.

*"Don't gain the world and lose your soul. Wisdom is better than silver or gold."* - Bob Marley