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

Home > Numbers
Strictly non-palindromic numbers (Posted on 2018-02-18) Difficulty: 3 of 5
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.)
Solution 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 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
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 (5)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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