Palindrome Numbers

erco

erco

Senior Member
A bit more complicated than my post about Kaprekar, this "fun fact" about Palindrome numbers may inspire some clever coding to see if a Picaxe can calculate 3 Palindrome numbers which add up to a target number. Enjoy and Happy New Year!

 
First I wanted to know, out of interest: How many Palindromes in a 16bit integer?
Answer: 754

I know, I didn't answer the original question correctly. I was never good at tests.
Teachers always baulked at my answers, but all agreed that I did have some strange inspiration.

Maybe, kudos for the slowest, wrong answer?

Rich (BB code): 
#rem

    PICAXE BASIC Program: Palindrome_Generator_v1.bas

    List all Palindromes representable in a 16‑bit unsigned integer(0–65535)

    Counted 754 palindrome numbers in ascending order
    Brute force method tests every integer
    Really, Really SLOOOOW !
    
    Time to Execute (FAST) = 209 Seconds
    Time to Execute (SLOW) = 216 Seconds
               Memory Used = 229 BYTES
    
    rhb.20251231
    
#endrem

#picaxe 08M2
#no_data
setfreq m32
#terminal 38400
pause 3000 ; wait for terminal to start

symbol n  = w0
symbol d0 = b2
symbol d1 = b3
symbol d2 = b4
symbol d3 = b5
symbol d4 = b6
symbol t  = w4

main:

    time = 0
       n = 0
    #rem
        for word = 0 to 65535
        bug(infinite loop) just the way integers work in a microcontroller 
        at 65535 when n is incremented the value rolls around to 0
        a for/loop never ends
        same for byte = 0 to 255 - byte variable rolls around to 0 - infinite loop
    #endrem
    
    do
        gosub GetDigits ; FASTER
        'gosub GetDigits2 ; SLOWER

        gosub CheckPalindrome

        if b7 = 1 then
            sertxd(#n,cr,lf)
        endif
    
        inc n 
    loop until n = 0 ; 65535 when n is incremented the value rolls around to 0

    t = time / 2 ; adjusted because of resonator speed 0.5 second per tick
    sertxd("Elapsed Time: ",#t," seconds",cr,lf)

end

' ---[ Extract digits (PICAXE-safe math) FASTER ]---

GetDigits: ; @hippy | @westaust55 style coding found in forum for SPI/clocking bit banging?

  d0 = n // 10
  d1 = n / 10 // 10
  d2 = n / 100 // 10
  d3 = n / 1000 // 10
  d4 = n / 10000 // 10

return

' ---[ Extract digits (built-in function) SLOWER ]---

GetDigits2:

  BINTOASCII n, d4, d3, d2, d1, d0
  
return

' ---[ Palindrome check (result in b7) ]---

CheckPalindrome:

  b7 = 0

  if n < 10 then
    b7 = 1
    return
  endif

  if n < 100 then
    if d0 = d1 then 
        b7 = 1
    end if
    return
  endif

  if n < 1000 then
    if d0 = d2 then 
        b7 = 1
    end if
    return
  endif

  if n < 10000 then
    if d0 = d3 and d1 = d2 then 
        b7 = 1
    end if
    return
  endif

  ' 5-digit (up to 65535)
  if d0 = d4 and d1 = d3 then 
      b7 = 1
  end if

return

' ---[EOF]---
Not the brightest bulb in the forum, but more like a slow blow fuse ... rhb. ;)
 
Last edited:
Hi,

It appears to be integer numbers of less than about 6 digits which involve most of the "special cases" for the solution/proof. Apparently the method also can be applied to numbers to any number-base except for base 2, i.e. binary, (which can require up to 4 palindromic numbers). Also, there was an "omission" in the original paper, which was corrected by one of the authors (and others).

There's an on-line engine to demonstrate the operation, including a link to its Source Code, which appears to be a couple of thousand lines of Javascript. :( :
the-incredible-palindromic-hat-trick/.

Incidentally, the time estimation in #2 above, may be a little optimistic, because the "time" variable (prescaler / incrementing) always stops during the SERTXD instructions.

So I think 'll stick with my aim of trying to solve a Rubik's cube using only a 14M2. ;)

Cheers, Alan.
 
Last edited:
AllyCat said:
Incidentally, the time estimation in #2 above, may be a little optimistic, because the "time" variable (prescaler / incrementing) always stops during the SERTXD instructions.
Click to expand...
Oh! Learned something new not found in the manuals, that the TIME command is a system variable and it can stop during certain commands. Time to add to my PICAXE Cheat Sheet.

Any other commands that could stop TIME?
 
Hi,

Basically, all the Instructions that the Operating System uses to Bit-Bang Serial Communications, i.e. also SERRXD, SEROUT, SERIN, IROUT, IRIN, RFOUT and RFIN (and DEBUG if ever used). "Time" uses the same (Interrupt Driven) Precaler as the Servo Outputs, so the same commands are known to sometimes cause Servos to glitch or judder. And of course DISABLETIME, although this command does Not actually stop the internal timer Interrupts.

One way to avoid the issue is to use the HSERIN and HSEROUT commands, and User Bit-Banging commands do not generally cause the problem, so may be a work-around for IR communications (e.g. SIRC and NEC protocols). AFAIK, other Bit-Banging commands such as PULSOUT, PULSIN and PAUSEUS do Not disable interrupts, so themselves may be slightly upset by the brief timer interrupt every 20 ms (or as determined by SETFREQ). There are some hints to all this, for example in the Appendix to Section/Manual 2, "Possible Conflicting Commands".

Cheers, Alan.
 
Why is the sum of three palindromic numbers special ?
Are there solutions with any other number of palindromes ?
Is three the minimum?

Obviously every number can be generated from sums of '1's, as 1' is a palindrome. Maybe sums of '11's and '1's can also be used, and then '111's and 1111's for bigger results. So I suppose any number be made from '1' based palindromes.

If you then use '101', '11011', '10101' type palindromes, which have a very binary feel to them, it would be cool to see what patterns emerge as the numbers get bigger.
 
Three is the minimum. E.g. 21 cannot be the sum of only two palindromes (the only available ones are 1-9 and 11).
 
Hi,

Three is the MAXIMUM number of necessary palindromes (needed to solve for ANY input number), because the initial number could be Palindromic itself and there can be (many) more two and three -palindrome solutions (partly depending whether you consider zero to be a palindromic number). Interestingly, binary is the (only) exception number-base, which may require the sum of FOUR palindromes to create the input number. But, (IMHO) this appears to be a rather "useless" theorem and I notice that the author in the link of #5 above lists it in his "Toys" section, not even as a "Game", let alone a "Useful Tool". ;)

Cheers, Alan.
 
I think this is partly a matter of semantics:
Three is the minimum number n such that any number can be written as the sum of n palindromes
Three is the maximum number n of palindromes required to sum to any number.
 
You must log in or register to reply here.
Back
Top