All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Feathers of different colors (Posted on 2018-10-06) Difficulty: 3 of 5
How many 3-digit primes with 3 distinct digits are there? Same question for 4 -digit primes with 4 distinct digits.

, Bonus: Generalize for n distinct primes and digits. (n=2 to 7).

AFAIK - not in OEIS.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer-assisted solution and extension (spoiler) | Comment 1 of 2
When I first read this puzzle, I thought it was an impossible enumeration task, thinking the categories would contain infinitely many examples, considering, for example, 1000211 to be an example of a prime with only three distinct digits: 0, 1 and 2. Then I realized a possible realistic interpretation: that no distinct digit appears more than once in the prime.

Those counts are:

 n   count

 1       4
 2      20
 3      97
 4     510
 5    2529
 6   10239
 7   33950
 8   90510
 9  145227

No 10-digit primes use all ten digits as all such numbers are multiples of 9. 
 
The counts for n = 1 to 7 were found by finding all the primes below 9999999 and categorizing them by length if they contained no duplicate digits. The counts for 8, 9 and 10 were found by permuting all the digits and testing the first 8, 9 or all, for primality. Care was taken to count the 8-digit numbers only once (digits 9 and 10, not used, in ascending order for the 8-digit number to be counted).

To make sure all permutations not beginning with zero were counted, the total permuations examined were 3265920 in number, which matches 10!-9!. I checked this as I took the shortcut of stopping the permuting once the string reached one beginning with zero, and I had to adjust the starting string so that no permutation would be lost.

Searching the sequence on the OEIS, I find in fact two occurrences of this sequence, one marked as merely the duplicate of another: A073532 (the original -- Number of n-digit primes with all digits distinct) and A098225 (the duplicate).

DefDbl A-Z
Dim crlf$, ct(10)

Function mform$(x, t$)
  a$ = Format$(x, t$)
  If Len(a$) < Len(t$) Then a$ = Space$(Len(t$) - Len(a$)) & a$
  mform$ = a$
End Function

Private Sub Form_Load()
 Text1.Text = ""
 crlf$ = Chr(13) + Chr(10)
 Form1.Visible = True
 
 p = 2
 Do
   s$ = LTrim(Str(p))
   l = Len(s)
   If l = 1 Then
     ct(1) = ct(1) + 1
   Else
     good = 1
     For i = 2 To Len(s)
       If InStr(s, Mid(s, i, 1)) < i Then good = 0: Exit For
     Next
     If good Then ct(l) = ct(l) + 1
   End If
   p = nxtprm(p)
   DoEvents
 Loop Until p > 9999999#
 
 For i = 1 To 7
   Text1.Text = Text1.Text & mform(i, "##") & mform(ct(i), "#######0") & crlf
 Next
 
 s$ = "1023456789": h$ = s
 Do
   p1 = Val(Left(s, 8))
   If Mid(s, 9, 1) < Mid(s, 10, 1) Then
     If prmdiv(p1) = p1 Then ct(8) = ct(8) + 1
   End If
   p2 = Val(Left(s, 9))
   If prmdiv(p2) = p2 Then ct(9) = ct(9) + 1
   p3 = Val(s)
   If prmdiv(p3) = p3 Then ct(10) = ct(10) + 1
   permute s
   tct = tct + 1
   DoEvents
 Loop Until Left(s, 1) = "0"
 
 For i = 8 To 10
   Text1.Text = Text1.Text & mform(i, "##") & mform(ct(i), "#########0") & crlf
 Next
 
 
 Text1.Text = Text1.Text & tct & crlf
 End Sub



Function prmdiv(num)
 Dim n, dv, q
 If num = 1 Then prmdiv = 1: Exit Function
 n = Abs(num): If n > 0 Then limit = Sqr(n) Else limit = 0
 If limit <> Int(limit) Then limit = Int(limit + 1)
 dv = 2: GoSub DivideIt
 dv = 3: GoSub DivideIt
 dv = 5: GoSub DivideIt
 dv = 7
 Do Until dv > limit
   GoSub DivideIt: dv = dv + 4 '11
   GoSub DivideIt: dv = dv + 2 '13
   GoSub DivideIt: dv = dv + 4 '17
   GoSub DivideIt: dv = dv + 2 '19
   GoSub DivideIt: dv = dv + 4 '23
   GoSub DivideIt: dv = dv + 6 '29
   GoSub DivideIt: dv = dv + 2 '31
   GoSub DivideIt: dv = dv + 6 '37
 Loop
 If n > 1 Then prmdiv = n
 Exit Function

DivideIt:
 Do
  q = Int(n / dv)
  If q * dv = n And n > 0 Then
    prmdiv = dv: Exit Function
   Else
    Exit Do
  End If
 Loop

 Return
End Function

Function nxtprm(x)
  Dim n
  n = x + 1
  While prmdiv(n) < n Or n < 2
    n = n + 1
  Wend
  nxtprm = n
End Function



  Posted by Charlie on 2018-10-06 11:28:05
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information