 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Strictly non-palindromic numbers (Posted on 2018-02-18) 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.

 No Solution Yet Submitted by Ady TZIDON No Rating Comments: ( Back to comment list | You must be logged in to post comments.) computer exploration and solution to 3.5 parts | Comment 1 of 3
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 147 3:       1 2 0 247 4:       2 3 347 5:       1 4 247 6:       1 1 547 7:       6 547 8:       5 747 9:       5 247 10:      4 747 11:      4 347 12:      3 1147 13:      3 847 14:      3 547 15:      3 247 16:      2 1547 17:      2 1347 18:      2 1147 19:      2 947 20:      2 747 21:      2 547 22:      2 347 23:      2 147 24:      1 2347 25:      1 2247 26:      1 2147 27:      1 2047 28:      1 1947 29:      1 1847 30:      1 1747 31:      1 1647 32:      1 1547 33:      1 1447 34:      1 1347 35:      1 1247 36:      1 1147 37:      1 1047 38:      1 947 39:      1 847 40:      1 747 41:      1 647 42:      1 547 43:      1 447 44:      1 347 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   representation5   2:      1 0 17   2:      1 1 113  3:      1 1 117  2:      1 0 0 0 123  3:      2 1 229  4:      1 3 131  2:      1 1 1 1 137  6:      1 0 141  5:      1 3 143  6:      1 1 159  4:      3 2 361  6:      1 4 167  5:      2 3 271  7:      1 3 173  2:      1 0 0 1 0 0 183  5:      3 1 389  8:      1 3 197  8:      1 4 1101 10:     1 0 1107 2:      1 1 0 1 0 1 1109 5:      4 1 4113 8:      1 6 1127 2:      1 1 1 1 1 1 1131 10:     1 3 1151 3:      1 2 1 2 1157 7:      3 1 3173 3:      2 0 1 0 2181 10:     1 8 1191 6:      5 1 5193 12:     1 4 1197 6:      5 2 5199 11:     1 7 1211 8:      3 2 3 227 8:      3 4 3229 12:     1 7 1233 3:      2 2 1 2 2239 14:     1 3 1241 12:     1 8 1251 8:      3 7 3257 2:      1 0 0 0 0 0 0 0 1271 7:      5 3 5277 11:     2 3 2281 14:     1 6 1307 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)

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 Please log in:

 Search: Search body:
Forums (0)