prime numbers whose digits are in strictly ascending order

T

Tamás-Haim

New member
Joined
Aug 14, 2020
Messages
9
Greetings!

I have found this:
There are exactly 100 prime numbers whose digits are in strictly ascending order
Wiki
(Obviously it is in base 10)

I think, that the biggest such number has max 8 digits, as the 9 digits long 123456789 is not prime.

Is it true?
What are these 100 numbers?
Is there a proof for it?
Who proved or counted them and when?



What is the situation in other bases?
Base 2: there is none.
Base 3: there is one = 12
Base 4: there are 3 = 12,13,23,123
Base x: ?

Thanks and greetings


Tamás-Haim
 
I just found 100 solutions for base 10
Code: 
  2     167    1367     5689      34679   
  3     179    1459    12347     123457  
  5     239    1489    12379     123479  
  7     257    1567    12457     124567  
 13     269    1579    12479     124679  
 17     347    1789    12569     125789  
 19     349    2347    12589     134789  
 23     359    2357    12689     145679  
 29     367    2389    13457     234589  
 37     379    2459    13469     235679  
 47     389    2467    13567     235789  
 59     457    2579    13679     245789  
 67     467    2689    13789     345679  
 79     479    2789    15679     345689  
 89     569    3457    23459    1234789 
127    1237    3467    23567    1235789 
137    1249    3469    23689    1245689 
139    1259    4567    23789    1456789
149    1279    4679    25679   12356789
157    1289    4789    34589   23456789

By programming a series of simple shell scripts...
Code: 
#!/bin/bash
# Show the 4 digit solutions
for a in  1 2 3 4 5 6; do
for b in  2 3 4 5 6 7; do
for c in  3 4 5 6 7 8; do
for d in  4 5 6 7 8 9; do
    if [ $a -lt $b  -a  $b -lt $c  -a  $c -lt $d ]; then
        p=$a$b$c$d
        factor $p | grep -qE '^(.*): \1$'
        if [ $? = 0 ]; then echo $p; fi
    fi
done
done
done
done
 
Thanks, Cubist! It was really very quick and helpful to me!

So, the statement is true in base 10!

I am still interested, how many are they in other bases?

Friendly greetings!
 
A brute force proof would be to list the numbers that, in decimal notation, have digits in ascending order, flag those that are primes, and count the number of flags. Obviously, the whole thing depends on what ascending order means. Does 1 even count? What does ascending order mean in a set with one element?
 
Hello Jeff!
Thanks for your message!

1 does not count, as it is not a prime number.

I am interested in prime numbers written in different bases.
So, dn should always be smaller than dn+1 in the given base. (numbering the digits from left to right)

Is there a rule which says that in a given base how many such numbers exist?
I speak here about big bases, like in base million, or base googol...
In small bases we can use the "brut force", yes. But with big numbers as base?




Thanks


Tamás-Haim
 
What I meant was whether 1 is a number with digits in ascending or descending order?
 
For me a one-digit number is ok, yes.
The 1, I would consider it ascending...
 
Last edited:
Well the first thing I would do is to see whether you can create a formula that says how many such numbers there are in a given base.
 
Hi, you raised a very interesting question. Rather then asking us to figure out what happens in another base why don't you try? Pick base 5 for example and see what you can do with it. If you need help along the way then someone here will assist you. That is true learning!
 
@Tamás-Haim , please try base 5 and let's see if you come up with 5^2=25 such numbers. It will be very interesting to see what you come up with!
 
Thank you, Jomo for showing interest in the question and for encouraging me.

Here are my manually calculated results:

base 2: zero
base 3: 2 (2,12 = 2,5)
base 4: 4 (2,3,13,23 = 2,3,7,11)
base 5: 5 (2,3,12,23,34 = 2,3,7,13,19)

(primes in the given base, their decimal values)

I have two ways in my mind to go further:
Start with the list of prime numbers, convert them into the given base, check if the digits are in the desired order
Or
Take in the given base the possible numbers (where the digits are in the appropriate order) and check them one by one if they are prime numbers (in any base it is enough to go up to numbers with base-1 digits)

I use an Android tablet.
With what tool should I program?

Thanks again!

Greetings

Tamas
 
Hi Jeff!

"Well the first thing I would do is to see whether you can create a formula that says how many such numbers there are in a given base."

Well, this is my goal... To create a formula which says how many prime number exists in a given base where the digits are in the desired order.

I am just experimenting with small bases to see if there is any pattern...

How would you create such a formula???
I have no idea how to create it...

Thanks


Tamás-Haim
 
How you create (actually conjecture) a formula? First you look at the sequence of numbers! Are they arithmetic or geometric, if yes then the formula is easily found. There are different techniques to try to find a pattern. One way is to think that it will follow a polynomial of some degree. Maybe the terms are all in the form of (the base number)^3. or you can use difference tables, etc. First get a correct list for base 1- base 10 (base 1 is easy and we know base 10 already) and we will go from there.
 
Cubist said:
I just found 100 solutions for base 10
Code: 
  2     167    1367     5689      34679 
  3     179    1459    12347     123457
  5     239    1489    12379     123479
  7     257    1567    12457     124567
13     269    1579    12479     124679
17     347    1789    12569     125789
19     349    2347    12589     134789
23     359    2357    12689     145679
29     367    2389    13457     234589
37     379    2459    13469     235679
47     389    2467    13567     235789
59     457    2579    13679     245789
67     467    2689    13789     345679
79     479    2789    15679     345689
89     569    3457    23459    1234789
127    1237    3467    23567    1235789
137    1249    3469    23689    1245689
139    1259    4567    23789    1456789
149    1279    4679    25679   12356789
157    1289    4789    34589   23456789

By programming a series of simple shell scripts...
Code: 
#!/bin/bash
# Show the 4 digit solutions
for a in  1 2 3 4 5 6; do
for b in  2 3 4 5 6 7; do
for c in  3 4 5 6 7 8; do
for d in  4 5 6 7 8 9; do
    if [ $a -lt $b  -a  $b -lt $c  -a  $c -lt $d ]; then
        p=$a$b$c$d
        factor $p | grep -qE '^(.*): \1$'
        if [ $? = 0 ]; then echo $p; fi
    fi
done
done
done
done
Click to expand...
@Cubist, would you mind running and posting the results for base 1 through base 10. I am curious to see what we find. Thanks!
 
Jomo said:
@Cubist, would you mind running and posting the results for base 1 through base 10. I am curious to see what we find. Thanks!
Click to expand...
I'm a sucker for a programming project! :geek: Here's what I found:-

base , #digit ascending primes
2 , 0
3 , 2
4 , 4
5 , 5
6 , 15
7 , 15
8 , 34
9 , 31
10 , 100
11 , 115
12 , 312
13 , 272
14 , 822
15 , 1452

Interesting that the result for base 9 is lower than base 8. EDIT base 13 takes a dip too!

Python: 
from itertools import combinations

def isPrime(x):
    if x==2: return 1
    if x<2 or x&1 == 0:
        return 0
    d=3
    while d*d <= x:
        if x%d == 0:
            return 0
        d += 2
    return 1

def toNum(lst,base):
    m=1
    rv=0
    for i in reversed(lst):
        rv += m*i
        m *= base
    return rv

maxBase=15
for base in range(2,maxBase+1):
    #print()
    count=0
    digits=list(range(1,base))
    for numDigits in range(1,base):
        for i in combinations(digits, numDigits):
            n=toNum(i,base)
            if isPrime(n):
                #print(n,"  ",i) # uncomment to display the individual numbers
                count+=1
    print(base, ",",count)
 
Last edited:
Actually, I was suggesting to start by searching for a different formula, namely how many numbers there are that, expressed in a given base, have digits that are in ascending order. We know there is a largest such number in each base, for example 123,456,789 in base 10, and that most numbers will not match the pattern, e.g. 21. So the number that are prime has an upper bound.
 
Thanks, Cubist! Yes, I did not expect at all, that the number could drop! Interesting.

Jeff, great point! (Sorry, I did not understand it when you wrote it the first time!) See first how many numbers, in a given base, respond to the ascending-digits criteria (I would guess the bigger the base the more they are) and then to see how many out of them are prime.

May I add questions? What about numbers where the digits are in strictly descending order? Like 9876543210...

(I was thinking to count the non-strictly ascending or descending digits, as well, however their numbers are infinite, as a given digit could be repeated forever.)
 
Cubist! I had to check what does the expression "I am a sucker for" means in English.. So, it means you like it.
:)
 
Cubist said:
I'm a sucker for a programming project! :geek: Here's what I found:-

base , #digit ascending primes
2 , 0
3 , 2
4 , 4
5 , 5
6 , 15
7 , 15
8 , 34
9 , 31
10 , 100
11 , 115
12 , 312
13 , 272
14 , 822
15 , 1452

Interesting that the result for base 9 is lower than base 8. EDIT base 13 takes a dip too!

Python: 
from itertools import combinations

def isPrime(x):
    if x==2: return 1
    if x<2 or x&1 == 0:
        return 0
    d=3
    while d*d <= x:
        if x%d == 0:
            return 0
        d += 2
    return 1

def toNum(lst,base):
    m=1
    rv=0
    for i in reversed(lst):
        rv += m*i
        m *= base
    return rv

maxBase=15
for base in range(2,maxBase+1):
    #print()
    count=0
    digits=list(range(1,base))
    for numDigits in range(1,base):
        for i in combinations(digits, numDigits):
            n=toNum(i,base)
            if isPrime(n):
                #print(n,"  ",i) # uncomment to display the individual numbers
                count+=1
    print(base, ",",count)
Click to expand...
Thanks for writing the program! Interesting results.

Seems like a base number with factors have something special going on. Also two digit base number (if that makes any sense :) ) start to take off.
There can be some nice results from this problem like giving a range of numbers for a given base. I never did like number theory but this is a little interesting. I would read the results and would give helpful hints if I see how to proceed but this is not a problem I would look into on my own, especially after seeing the results given by Cubist
 
This was my first question in this forum. Nice community, friendly and helping answers.
My main question was to check the number 100. And if it's done.

For the time being I would stop here...

Thanks for all the help!

Btw, I have another idea:
In a given base it I repeat a digit n times how many of this numbers could be prime.
Example: in base 2: 11,111,1111,11111 (3,7,15,31) or in base 3: 11,111,1111,22,222 (4,13,40,8,,26)
It seems that repeated even digits result even numbers, so they are not primes, for sure.
May be other eliminating rules?
Just a question, an idea...

Greetings

Tamas
 
You must log in or register to reply here.
Top