Definition: Strictly non-palindromic number or SNP number n is a number not palindromic in any base b with 2 ≤ b ≤ n-2.
Equipped only with the above definition you are asked to perform the following tasks:
1. Show that 47 is a SNP number.
2. Write down the 1st 7 members of an increasing sequence of SNP numbers.
3. Explain the reason for defining b=n-2 as the upper limit.
4. Prove that all SNP numbers above 6 are prime, but not all primes are SNP numbers.
Rearranging the output of the program at the bottom:
1. The number 47 in the various (all are non-palindromic) bases:
n base base representation
(digits of the base representation
are each shown in decimal notation)
47 2: 1 0 1 1 1 1
47 3: 1 2 0 2
47 4: 2 3 3
47 5: 1 4 2
47 6: 1 1 5
47 7: 6 5
47 8: 5 7
47 9: 5 2
47 10: 4 7
47 11: 4 3
47 12: 3 11
47 13: 3 8
47 14: 3 5
47 15: 3 2
47 16: 2 15
47 17: 2 13
47 18: 2 11
47 19: 2 9
47 20: 2 7
47 21: 2 5
47 22: 2 3
47 23: 2 1
47 24: 1 23
47 25: 1 22
47 26: 1 21
47 27: 1 20
47 28: 1 19
47 29: 1 18
47 30: 1 17
47 31: 1 16
47 32: 1 15
47 33: 1 14
47 34: 1 13
47 35: 1 12
47 36: 1 11
47 37: 1 10
47 38: 1 9
47 39: 1 8
47 40: 1 7
47 41: 1 6
47 42: 1 5
47 43: 1 4
47 44: 1 3
47 45: 1 2
None of the representations is palindromic.
2. The first seven SNP's:
4
6
11
19
47
53
79
and the remainder of the first twenty:
103
137
139
149
163
167
179
223
263
269
283
293
311
3. All numbers are palindromic in base n-1, where its representation is 11. No numbers are palindromic in base n, as each is 10 in that base. In all bases above n, the representation is just the digit representing n, a degenerate palindrome.
4. It's obvious that not all primes are SNP's, as for example, 13 is not an SNP (in base 3 it is 111) and 181 is palindromic in base ten.
Other palindromic representations of primes:
n base representation
5 2: 1 0 1
7 2: 1 1 1
13 3: 1 1 1
17 2: 1 0 0 0 1
23 3: 2 1 2
29 4: 1 3 1
31 2: 1 1 1 1 1
37 6: 1 0 1
41 5: 1 3 1
43 6: 1 1 1
59 4: 3 2 3
61 6: 1 4 1
67 5: 2 3 2
71 7: 1 3 1
73 2: 1 0 0 1 0 0 1
83 5: 3 1 3
89 8: 1 3 1
97 8: 1 4 1
101 10: 1 0 1
107 2: 1 1 0 1 0 1 1
109 5: 4 1 4
113 8: 1 6 1
127 2: 1 1 1 1 1 1 1
131 10: 1 3 1
151 3: 1 2 1 2 1
157 7: 3 1 3
173 3: 2 0 1 0 2
181 10: 1 8 1
191 6: 5 1 5
193 12: 1 4 1
197 6: 5 2 5
199 11: 1 7 1
211 8: 3 2 3
227 8: 3 4 3
229 12: 1 7 1
233 3: 2 2 1 2 2
239 14: 1 3 1
241 12: 1 8 1
251 8: 3 7 3
257 2: 1 0 0 0 0 0 0 0 1
271 7: 5 3 5
277 11: 2 3 2
281 14: 1 6 1
307 7: 6 1 6
That all SNP's above 6 are prime is harder to prove. At least it's not obvious.
Looking at some other output, not shown, gives some insights as to what to look for:
If the base is 1 less than its largest factor then the representation is the quotient of the number divided by that factor, repeated twice; for example, ten in base 4 is 22, as ten's largest factor is 5 and 10/5 = 2. This doesn't work for n=6 as 1 less than its largest factor, 3, is 2, and 6/3 = 2, which can't be used in base 2.
That leaves the question of squares of primes (or in fact non-primes, where it's less needed), say 9 or 49. If we use a base that's one less than the square root the original number then n = (b+1)^2 = b^2 + 2*b + 1, leading to a representation of n in base b as 121, such as 49 in base 6: 121 in base 6 as 36 + 12 + 1 = 49. That leaves just 9 itself, since 2 is not a digit in base 2. However 9 is indeed 1001 in binary and is shown as a special case.
DefDbl A-Z
Dim crlf$, baseRep(50)
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
For n = 4 To 1000
good = 1
For b = 2 To n - 2
baseCon n, b
If n = 47 Then
Text1.Text = Text1.Text & "47 " & b & ": "
For i = baseRep(0) To 1 Step -1
Text1.Text = Text1.Text & Str(baseRep(i))
Next
Text1.Text = Text1.Text & crlf
End If
If isRepPalin Then
' If prmdiv(n) = n Then
Text1.Text = Text1.Text & Str(n) & " " & b & ": "
For i = baseRep(0) To 1 Step -1
Text1.Text = Text1.Text & Str(baseRep(i))
Next
Text1.Text = Text1.Text & crlf
' End If
good = 0
Exit For
End If
DoEvents
Next
If good Then
Text1.Text = Text1.Text & n & crlf
ct = ct + 1
If ct = 20 Then Exit For
End If
Next n
Text1.Text = Text1.Text & crlf & " done"
End Sub
Function isRepPalin()
good = 1
For i = 1 To baseRep(0) / 2
If baseRep(i) <> baseRep(baseRep(0) + 1 - i) Then good = 0: Exit For
Next
isRepPalin = good
End Function
Sub baseCon(n, b)
baseRep(0) = 0
n2 = n
Do
d = n2 Mod b
n2 = n2 \ b
baseRep(0) = baseRep(0) + 1
baseRep(baseRep(0)) = d
Loop Until n2 = 0
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
|
|
Posted by Charlie
on 2018-02-18 12:07:57 |
computer exploration and solution to 3.5 parts
