User avatar
RichardRussell
Posts: 1112
Joined: Thu Jun 21, 2012 10:48 am

Re: Double base palindromes

Fri Sep 24, 2021 8:25 pm

RichardRussell wrote:
Fri Sep 24, 2021 7:45 pm
There are only 17 known numbers which are palindromes in both base-2 and base-3
Here's a BBC BASIC program which will find the first six of these numbers (including the trivial ones). It will run on the Pico, so it's on-topic, but it's quite slow on that platform:

Code: Select all

   10 @%=&1414
   20 *HEX 64
   30
   40 PRINT "Numbers which are palindromic in base-2 and base-3:"
   50 PROCa(0,36,0)
   60 END
   70
   80 DEF PROCa(x%%,N%,B%)
   90 IF N%<0 THEN
  100   PROCb(x%%,3)
  110 ELSE
  120   PROCa(x%%,N%-2,B%<>0 AND B%+1)
  130   PROCa(x%% OR 1<<B% OR 1<<(B%+N%),N%-2,B%+1)
  140 ENDIF
  150 ENDPROC
  160
  170 DEF PROCb(x%%,B%)
  180 LOCAL p%%,q%%
  190 p%%=x%%
  200 IF x%% q%%=B%^INT(LNx%%/LNB%)
  210 WHILE p%%
  220   IF (x%%DIVq%%MODB%)<>(p%%MODB%) ENDPROC
  230   p%%DIV=B% : q%%DIV=B%
  240 ENDWHILE
  250 PRINT x%%
  260 ENDPROC

Code: Select all

Numbers which are palindromic in base-2 and base-3:
                   0
                   1
                6643
             1422773
             5415589
         90396755477

ejolson
Posts: 8613
Joined: Tue Mar 18, 2014 11:47 am

Re: Double base palindromes

Sat Sep 25, 2021 1:44 am

RichardRussell wrote:
Fri Sep 24, 2021 8:25 pm
RichardRussell wrote:
Fri Sep 24, 2021 7:45 pm
There are only 17 known numbers which are palindromes in both base-2 and base-3
Here's a BBC BASIC program which will find the first six of these numbers (including the trivial ones). It will run on the Pico, so it's on-topic, but it's quite slow on that platform:

Code: Select all

   10 @%=&1414
   20 *HEX 64
   30
   40 PRINT "Numbers which are palindromic in base-2 and base-3:"
   50 PROCa(0,36,0)
   60 END
   70
   80 DEF PROCa(x%%,N%,B%)
   90 IF N%<0 THEN
  100   PROCb(x%%,3)
  110 ELSE
  120   PROCa(x%%,N%-2,B%<>0 AND B%+1)
  130   PROCa(x%% OR 1<<B% OR 1<<(B%+N%),N%-2,B%+1)
  140 ENDIF
  150 ENDPROC
  160
  170 DEF PROCb(x%%,B%)
  180 LOCAL p%%,q%%
  190 p%%=x%%
  200 IF x%% q%%=B%^INT(LNx%%/LNB%)
  210 WHILE p%%
  220   IF (x%%DIVq%%MODB%)<>(p%%MODB%) ENDPROC
  230   p%%DIV=B% : q%%DIV=B%
  240 ENDWHILE
  250 PRINT x%%
  260 ENDPROC
That's an astonishing recursive algorithm. How does it work?

The article by Keith Lynch

http://chesswanks.com/txt/BigDualPalindromes.txt

seems particularly relevant to the search for large dual-base palindromes. It would appear such numbers are much more difficult to find than, for example, large primes as there are far more primes. I wonder if one would have any luck starting with a random prefix corresponding to a number above 3^93 and searching for double palindromes after that.

I downloaded the list

Code: Select all

1 0
2 1
3 6643
4 1422773
5 5415589
6 90396755477
7 381920985378904469
8 1922624336133018996235
9 2004595370006815987563563
10 8022581057533823761829436662099
11 392629621582222667733213907054116073
12 32456836304775204439912231201966254787
13 428027336071597254024922793107218595973
14 1597863243206403857787246920544522912361
15 30412638162199251273509758127730300026189
16 32345684491703244980406880704479906642045
17 24014998963383302600955162866787153652444049
https://oeis.org/A060792/b060792.txt

of all known numbers that are palindromes in bases 2 and 3. To double-check that none of them are also palindromes in base 5 I typed

Code: Select all

$ ( echo "obase=5"; cut -d" " -f2 b060792.txt ) | bc
0
1
203033
331012043
2341244324
2440113032133402
11200433121411023444420334
2013011120213441200410330334420
32102202104224200013133120304013223
120120212241232423003143241102303141241141344
420224203132041043000231311312010303123121323203243
243020343200313440034442430312240401432003111330123122
12323403443012013134042310031112444420314232040430032343
103343013224422000311442221332304430211332200140331143421
4142413041302122331022110123411243121114304213123301314224
4312321000343303000342031011442302000320144144322100021140
102320430340043430244023403432033232243331201011211140011202144
Nope, none of those except the first two are base-5 palindromes.

I wonder how many Pico computers it would take to find the 18th number on that list (if there is one). Given the size and cost of each device, a Pico@home distributed computing project could easily surpass SETI@home. Unfortunately, the Pico is out of stock at most of the retailers I checked. Were they all bought up to search for double-base palindromes already?

User avatar
RichardRussell
Posts: 1112
Joined: Thu Jun 21, 2012 10:48 am

Re: Double base palindromes

Sat Sep 25, 2021 11:52 am

ejolson wrote:
Sat Sep 25, 2021 1:44 am
That's an astonishing recursive algorithm. How does it work?
It's a binary palindrome generator (on the basis that the quickest way to find the double palindromes is to generate all base-2 palindromes and then test if they are also palindromic in base-3). Basically it's iteratively creating all palindromic bit patterns up to the number of bits specified, so for example this sets two more bits in such a way that the number remains palindromic:

Code: Select all

x%% OR 1<<B% OR 1<<(B%+N%)
There's a minor simplification in that (apparently - I'm no mathematician) it's easy to prove that any number that is palindromic in two consecutive bases (such as 2 and 3) must have an odd number of digits, so I only generate base-2 palindromes with an odd number of bits.

WestfW
Posts: 123
Joined: Tue Nov 01, 2011 9:56 pm

Re: Double base palindromes

Sat Sep 25, 2021 11:04 pm

That's an astonishing recursive algorithm. How does it work?
It's a binary palindrome generator
Presumably, a palindrome is either a "trivial palindrome" (1 or 11, in binary), or a previously known palindrome with the same digit appended to both ends. (n*base + digit + digit*(base**length)) or (n*base + digit *(1 + (base**length))
(Hmm. Plus the cases with zeros in the middle.)

So now we can generate palindromes in any base, and we can check them in any base (somewhat slowly, using the stringify algorithm from early posts.)

Someone said that the density of palindromes is independent of base. That seems to be true (I count 1999 binary palindromes up to 1e6, compared to 1998 for decimal.) Seems reasonable - the number of digits goes up and the number of possible values of each digit goes down... ~2*sqrt(N) palindromes for 0...N-1 ?

pidd
Posts: 2788
Joined: Fri May 29, 2020 8:29 pm
Location: Wirral, UK
Contact: Website

Re: Double base palindromes

Sat Sep 25, 2021 11:49 pm

I always saw palindromes as NOT being a mathematical function - its more like a language construct than arithmetical. Until I saw the following ....

If a palindrome has an even number of digits then its position (index) can be calculated like so:-

Take the first half of the digits and put a "1" in front eg 234432 will be in the 1234th position.

If a palindrome has an odd number of digits:-

Take the first half of the digits including the middle digit, then add one to the fist digit eg 123454321 will be in the 22345th position.

This shows that palindromes can be counted, counting is the very basis on numbers and therefore palindromes are a arithmetical/mathematical function.

SOURCE

User avatar
RichardRussell
Posts: 1112
Joined: Thu Jun 21, 2012 10:48 am

Re: Double base palindromes

Sun Sep 26, 2021 9:16 am

WestfW wrote:
Sat Sep 25, 2021 11:04 pm
Presumably, a palindrome is either a "trivial palindrome" (1 or 11, in binary), or a previously known palindrome with the same digit appended to both ends
Well, if you add a zero to both ends you don't end up with a new palindrome (since by definition the number cannot start with - or end with - a zero digit) so you can't enumerate them quite like that.
somewhat slowly, using the stringify algorithm from early posts.
I can't really see the appeal of an algorithm that involves conversion to a string, other than it being trivial to understand, when it's possible to test for a numeric palindrome using arithmetic/logical operations alone. That's especially true since you can eliminate many of the candidate values by discovering that the first and last digits are different, and it's wasteful to generate the entire string only for it to be rejected for that reason.

hippy
Posts: 10938
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: Double base palindromes

Sun Sep 26, 2021 12:51 pm

RichardRussell wrote:
Sun Sep 26, 2021 9:16 am
I can't really see the appeal of an algorithm that involves conversion to a string, other than it being trivial to understand, when it's possible to test for a numeric palindrome using arithmetic/logical operations alone
For some interpreted languages; conversion to a string, reversal and comparison done internally will be quicker than iterative tests done in the language being interpreted.

I haven't benchmarked it but I would expect this Python code for finding decimal palindromes will be pretty fast -

Code: Select all

s = str(n)
if s == s[::-1]:
  print("Decimal palindrome : {}".format(n))

ejolson
Posts: 8613
Joined: Tue Mar 18, 2014 11:47 am

Re: Double base palindromes

Sun Sep 26, 2021 1:17 pm

hippy wrote:
Sun Sep 26, 2021 12:51 pm
RichardRussell wrote:
Sun Sep 26, 2021 9:16 am
I can't really see the appeal of an algorithm that involves conversion to a string, other than it being trivial to understand, when it's possible to test for a numeric palindrome using arithmetic/logical operations alone
For some interpreted languages; conversion to a string, reversal and comparison done internally will be quicker than iterative tests done in the language being interpreted.

I haven't benchmarked it but I would expect this Python code for finding decimal palindromes will be pretty fast -

Code: Select all

s = str(n)
if s == s[::-1]:
  print("Decimal palindrome : {}".format(n))
Am I right you said earlier

viewtopic.php?p=1913261#p1913261

that microPython on the Pico doesn't support this way of reversing strings?

lurk101
Posts: 1061
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Double base palindromes

Sun Sep 26, 2021 3:04 pm

RichardRussell wrote:
Sun Sep 26, 2021 9:16 am
I can't really see the appeal of an algorithm that involves conversion to a string, other than it being trivial to understand, when it's possible to test for a numeric palindrome using arithmetic/logical operations alone.
It is an advantage being able to test without needing to rebase the whole number, but by testing using arithmetic operations (other than for base 2) wouldn't you be doing the same as a string conversion. Namely, a bunch of integer divide and remainder operation?

hippy
Posts: 10938
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: Double base palindromes

Sun Sep 26, 2021 3:17 pm

ejolson wrote:
Sun Sep 26, 2021 1:17 pm
hippy wrote:
Sun Sep 26, 2021 12:51 pm
RichardRussell wrote:
Sun Sep 26, 2021 9:16 am
I can't really see the appeal of an algorithm that involves conversion to a string, other than it being trivial to understand, when it's possible to test for a numeric palindrome using arithmetic/logical operations alone
For some interpreted languages; conversion to a string, reversal and comparison done internally will be quicker than iterative tests done in the language being interpreted.

I haven't benchmarked it but I would expect this Python code for finding decimal palindromes will be pretty fast -

Code: Select all

s = str(n)
if s == s[::-1]:
  print("Decimal palindrome : {}".format(n))
Am I right you said earlier

viewtopic.php?p=1913261#p1913261

that microPython on the Pico doesn't support this way of reversing strings?
That is why I wrote " this Python code" not "this MicroPython code",

ejolson
Posts: 8613
Joined: Tue Mar 18, 2014 11:47 am

Re: Double base palindromes

Sun Sep 26, 2021 3:25 pm

lurk101 wrote:
Sun Sep 26, 2021 3:04 pm
RichardRussell wrote:
Sun Sep 26, 2021 9:16 am
I can't really see the appeal of an algorithm that involves conversion to a string, other than it being trivial to understand, when it's possible to test for a numeric palindrome using arithmetic/logical operations alone.
It is an advantage being able to test without needing to rebase the whole number, but by testing using arithmetic operations (other than for base 2) wouldn't you be doing the same as a string conversion. Namely, a bunch of integer divide and remainder operation?
Aside from being able to short-circuit the string conversion when a non-matching digit is found, in a compiled language the divisions and bit operations can be done in registers without the need to write any strings to memory.

While that memory will likely stay in cache long enough to check if the number is a palindrome, the main reasons strings seem useful is when the numbers being checked are too big to fit in a register and for interpreted languages where loops run much slower than the compiled loops in the support libraries.
Last edited by ejolson on Sun Sep 26, 2021 3:42 pm, edited 9 times in total.

ejolson
Posts: 8613
Joined: Tue Mar 18, 2014 11:47 am

Re: Double base palindromes

Sun Sep 26, 2021 3:28 pm

hippy wrote:
Sun Sep 26, 2021 3:17 pm
ejolson wrote:
Sun Sep 26, 2021 1:17 pm
hippy wrote:
Sun Sep 26, 2021 12:51 pm

For some interpreted languages; conversion to a string, reversal and comparison done internally will be quicker than iterative tests done in the language being interpreted.

I haven't benchmarked it but I would expect this Python code for finding decimal palindromes will be pretty fast -

Code: Select all

s = str(n)
if s == s[::-1]:
  print("Decimal palindrome : {}".format(n))
Am I right you said earlier

viewtopic.php?p=1913261#p1913261

that microPython on the Pico doesn't support this way of reversing strings?
That is why I wrote " this Python code" not "this MicroPython code",
Thanks for the confirmation. Are there any versions of Python for the Pico where one can use slices with a negative stride to reverse a string? It would seem like a useful addition to Micro Python.

lurk101
Posts: 1061
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Double base palindromes

Sun Sep 26, 2021 4:25 pm

ejolson wrote:
Sun Sep 26, 2021 3:25 pm
lurk101 wrote:
Sun Sep 26, 2021 3:04 pm
RichardRussell wrote:
Sun Sep 26, 2021 9:16 am
I can't really see the appeal of an algorithm that involves conversion to a string, other than it being trivial to understand, when it's possible to test for a numeric palindrome using arithmetic/logical operations alone.
It is an advantage being able to test without needing to rebase the whole number, but by testing using arithmetic operations (other than for base 2) wouldn't you be doing the same as a string conversion. Namely, a bunch of integer divide and remainder operation?
Aside from being able to short-circuit the string conversion when a non-matching digit is found, in a compiled language the divisions and bit operations can be done in registers without the need to write any strings to memory.
Interesting idea. How would you extract the leftmost digit in any base? First you'd need to determine its position using some kind of log function for that base which again needs a bunch of integer divides? Pretty much the same as converting it to a string.

Do you have working code?

hippy
Posts: 10938
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: Double base palindromes

Sun Sep 26, 2021 4:51 pm

ejolson wrote:
Sun Sep 26, 2021 3:28 pm
Are there any versions of Python for the Pico where one can use slices with a negative stride to reverse a string? It would seem like a useful addition to Micro Python.
MicroPython would support it if it were not "not implemented" -

~/pico/micropython/py/objarray.c
~/pico/micropython/py/objstr.c
~/pico/micropython/py/objstrunicode.c
~/pico/micropython/py/objtuple.c

For this challenge it appears only 'objstrunicode.c' needs fixing and only [::-1] needs supporting. I have tried doing that but haven't completed it yet; again hampered by "not a C programmer" though I'm sure all my MicroPython hacking is improving both my C and 'cmake' skills.

There is 'list(reversed(mystring))' which could be used but I'm not convinced that helps in terms of speeding things up.

It would be easier for me to add a built-in string reversal method, plus a 'bin()' which doesn't prefix "0b". In fact it would be easier to have a built-in method which takes a string and returns if palindromic or not. But all that's straying into 'cheating' territory, jumping out of MicroPython into C.

Of course all MicroPython is jumping into C but at least [::-1] is a defined part of its language, simply not implemented.

ejolson
Posts: 8613
Joined: Tue Mar 18, 2014 11:47 am

Re: Double base palindromes

Sun Sep 26, 2021 5:23 pm

hippy wrote:
Sun Sep 26, 2021 4:51 pm
ejolson wrote:
Sun Sep 26, 2021 3:28 pm
Are there any versions of Python for the Pico where one can use slices with a negative stride to reverse a string? It would seem like a useful addition to Micro Python.
MicroPython would support it if it were not "not implemented" -

~/pico/micropython/py/objarray.c
~/pico/micropython/py/objstr.c
~/pico/micropython/py/objstrunicode.c
~/pico/micropython/py/objtuple.c

For this challenge it appears only 'objstrunicode.c' needs fixing and only [::-1] needs supporting. I have tried doing that but haven't completed it yet; again hampered by "not a C programmer" though I'm sure all my MicroPython hacking is improving both my C and 'cmake' skills.

There is 'list(reversed(mystring))' which could be used but I'm not convinced that helps in terms of speeding things up.

It would be easier for me to add a built-in string reversal method, plus a 'bin()' which doesn't prefix "0b". In fact it would be easier to have a built-in method which takes a string and returns if palindromic or not. But all that's straying into 'cheating' territory, jumping out of MicroPython into C.

Of course all MicroPython is jumping into C but at least [::-1] is a defined part of its language, simply not implemented.
When it comes to getting things done, my impression is that people constantly jump between Python and other languages. For example, all that machine learning stuff people do with Python is really calls to C and CUDA software libraries.

It's not cheating, but simply how Python is used in many contexts. The same holds true for R where many of the libraries are written in C for performance. The only problem, as you've mentioned, is that it's often more difficult to produce and debug software written in multiple languages. Once the Python programmer needs to do something new or original they suddenly need to be a C programmer a well.

According to the dog developer, using two programming languages simultaneously in a single project is even more difficult than finding a number that's simultaneously a palindrome in two different bases. I'm not convinced, as the 18th number on that list of base 2 and 3 palindromes is still at large and waiting to be discovered.

And what about finding a number that is a simultaneously a palindrome is bases 2, 3 and 5? Would it help to simultaneously use three programming languages for that?

Time will tell if next-generation languages such as Julia are able to combine the performance of a compiler with the interactive environment of an interpreter. My suspicion is the trade-off between these two objectives is not as great as many people think they are.

Unfortunately, creating an interactive JIT programming environment for the Pico may prove too difficult for even Fido.
Last edited by ejolson on Sun Sep 26, 2021 6:51 pm, edited 1 time in total.

lurk101
Posts: 1061
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Double base palindromes

Sun Sep 26, 2021 5:41 pm

ejolson wrote:
Sun Sep 26, 2021 5:23 pm
According to the dog developer, using two programming languages simultaneously in a single project is even more difficult than finding a number simultaneously a palindrome in two different bases. I'm not convinced, as the 18th number on that list of base 2 and 3 palindromes is still at large and waiting to be discovered.
I wonder how much extra CO2 would be released into the atmosphere trying to find out? Bitcoin gets a bad rap for that, should the scientific community as well for frivolous use of supercomputers?

hippy
Posts: 10938
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: Double base palindromes

Sun Sep 26, 2021 5:59 pm

ejolson wrote:
Sun Sep 26, 2021 5:23 pm
When it comes to getting things done, my impression is that people constantly jump between Python and other languages. For example, all that machine learning stuff people do with Python is really calls to C and CUDA software libraries.

It's not cheating, but simply how Python is used in many contexts.
For getting things done generally, yes, but it's more dubious when implementing algorithm challenges. As noted earlier my MicroPython solution -

Code: Select all

import DoItInC
Would be just few microseconds slower than whatever C version it actually was.

This is why I said I wasn't clear on what the rules are for jumping out of a language and using C or Assembler, what amounts to 'cheating' and what does not.

ejolson
Posts: 8613
Joined: Tue Mar 18, 2014 11:47 am

Re: Double base palindromes

Sun Sep 26, 2021 6:07 pm

lurk101 wrote:
Sun Sep 26, 2021 5:41 pm
ejolson wrote:
Sun Sep 26, 2021 5:23 pm
According to the dog developer, using two programming languages simultaneously in a single project is even more difficult than finding a number simultaneously a palindrome in two different bases. I'm not convinced, as the 18th number on that list of base 2 and 3 palindromes is still at large and waiting to be discovered.
I wonder how much extra CO2 would released into the atmosphere trying to find out? Bitcoin gets a bad rap for that, should the scientific community as well?
Although it's important to distinguish the consumption of a natural resource from waste of one, given all the talk about dual base palindromes in this thread, maybe the exhaled CO2 is already greater than Bitcoin. Is it possible that dual-base palindromes, like all types of cryptocurrency, will be outlawed in China?

Unfortunately, much worse environmental dangers are largely ignored by the activists. Like many microbenchmarks, the end result after focused optimization is often worse.

Politics aside, since all numbers on the known list of base 2 and 3 palindromes easily fit in the memory of the Pico, it is reasonable to believe that the next one would fit as well. Therefore, the search for the 18th entry on that list could be a problem suitable for Pico@home and the consumption of energy similar to drinking a glass of water during the drought.

lurk101
Posts: 1061
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Double base palindromes

Sun Sep 26, 2021 6:12 pm

hippy wrote:
Sun Sep 26, 2021 5:59 pm
This is why I said I wasn't clear on what the rules are for jumping out of a language and using C or Assembler, what amounts to 'cheating' and what does not.
Using the PIO to reverse bits was never mentioned as cheating. It follows that invoking C or Assembler shouldn't be either.

I can't wait for the 'do_the_whole_thing_in_C' function call single line program. :P

lurk101
Posts: 1061
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Double base palindromes

Sun Sep 26, 2021 6:22 pm

ejolson wrote:
Sun Sep 26, 2021 6:07 pm
Politics aside, since all numbers on the known list of base 2 and 3 palindromes easily fit in the memory of the Pico, it is reasonable to believe that the next one would fit as well. Therefore, the search for the 18th entry on that list could be a problem suitable for Pico@home and the consumption of energy similar to drinking a glass of water during the drought.
I'd gladly volunteer a dozen Picos to Pico@home. But that's for a different thread. It's actually feasible with the help of a Pi0/3/4, and who knows? A few hobbyist might play just for fun. A ton of technicalities there. Seems a fine way to make use of energy.

ejolson
Posts: 8613
Joined: Tue Mar 18, 2014 11:47 am

Re: Double base palindromes

Sun Sep 26, 2021 7:40 pm

lurk101 wrote:
Sun Sep 26, 2021 6:22 pm
ejolson wrote:
Sun Sep 26, 2021 6:07 pm
Politics aside, since all numbers on the known list of base 2 and 3 palindromes easily fit in the memory of the Pico, it is reasonable to believe that the next one would fit as well. Therefore, the search for the 18th entry on that list could be a problem suitable for Pico@home and the consumption of energy similar to drinking a glass of water during the drought.
I'd gladly volunteer a dozen Picos to Pico@home. But that's for a different thread. It's actually feasible with the help of a Pi0/3/4, and who knows? A few hobbyist might play just for fun. A ton of technicalities there. Seems a fine way to make use of energy.
Do Pico's have any kind of serial number?

The search space is so large that a single unique seed could be used to parallelize the search for base 2, 3 palindromes across the entire Pico@home project--no network required. However, maybe there aren't any more base 2, 3 palindromes.

hippy
Posts: 10938
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: Double base palindromes

Sun Sep 26, 2021 7:44 pm

lurk101 wrote:
Sun Sep 26, 2021 6:12 pm
can't wait for the 'do_the_whole_thing_in_C' function call single line program. :P
It's basically this, implementing your C algorithm from your second post in this thread -

~/pico/micropython/ports/rp2/modules-c/doitinc/doitinc.c

Code: Select all

#include "py/dynruntime.h"

int palindrome(char* p) {
    int i, l = strlen(p);
    for (i = 0; i < l / 2; i++)
        if (p[i] != p[l - i - 1])
            return 0;
    return 1;
}

STATIC mp_obj_t run(void) {
    int sum = 0;
    for (int p = 1; p <= 1000000; p++) {
        char cbase[32];
        itoa(p, cbase, 10);
        if (palindrome(cbase)) {
            itoa(p, cbase, 2);
            if (palindrome(cbase))
                sum += p;
        }
    }
    return mp_obj_new_int(sum);
}
STATIC MP_DEFINE_CONST_FUN_OBJ_0(run_obj, run);

mp_obj_t mpy_init(mp_obj_fun_bc_t *self, size_t n_args, size_t n_kw, mp_obj_t *args) {
    MP_DYNRUNTIME_INIT_ENTRY
    mp_store_global(MP_QSTR_run, MP_OBJ_FROM_PTR(&run_obj));
    MP_DYNRUNTIME_INIT_EXIT
}
Unfortunately, because MicroPython has limited options for dynamically loaded libraries you have to provide 'strlen' and 'itoa' implementations in that source file, #include "strings" etc will not work - or more correctly I have never figured out how to make them work.

But once that's done, all you need is a Makefile -

~/pico/micropython/ports/rp2/modules-c/doitinc/Makefile

Code: Select all

MPY_DIR = /home/pi/pico/micropython
MOD     = DoItInC
SRC     = doitinc.c
ARCH    = armv6m
include $(MPY_DIR)/py/dynruntime.mk
Then compile it to create a '.mpy' file-

Code: Select all

pi@Pi3B:~/pico/micropython/ports/rp2/modules-c/doitinc $ make
GEN build/DoItInC.config.h
CC doitinc.c
LINK build/doitinc.o
arch:         EM_ARM
text size:    112
bss size:     0
GOT entries:  2
GEN DoItInC.mpy
pi@Pi3B:~/pico/micropython/ports/rp2/modules-c/doitinc $ ls
build  doitinc.c  DoItInC.mpy  Makefile
Copy the 'DoItInC.mpy' to the MicroPython file system root or /lib. Then on the Pico -

Code: Select all

>>> import DoItInC; print("Sum is {}".format(DoItInC.run()))
Sum is ...
>>> 
There should be a way to have it auto-run when imported and print directly to the console but I didn't bother investigating how to do that at this time but it's on my To Do list.

The above 'make' and on-Pico execution is partially faked because I commented out the actual palindrome checking code. I have 'strlen' but not an 'itoa' so it actually returns a sum of zero.

User avatar
RichardRussell
Posts: 1112
Joined: Thu Jun 21, 2012 10:48 am

Re: Double base palindromes

Sun Sep 26, 2021 9:13 pm

lurk101 wrote:
Sun Sep 26, 2021 4:25 pm
How would you extract the leftmost digit in any base?
I listed my BBC BASIC code to do that earlier in the thread, and yes it uses logs.
Pretty much the same as converting it to a string.
The common algorithm for converting a number to a string (in a given base) discovers the most-significant digit last of all, in other words by the time the MS digit is known the entire string is known. This is potentially wasteful if knowing just the MS and LS digits allows you to eliminate it as a palindrome.

ejolson
Posts: 8613
Joined: Tue Mar 18, 2014 11:47 am

Re: Double base palindromes

Mon Sep 27, 2021 12:10 am

ejolson wrote:
Sun Sep 26, 2021 7:40 pm
lurk101 wrote:
Sun Sep 26, 2021 6:22 pm
ejolson wrote:
Sun Sep 26, 2021 6:07 pm
Politics aside, since all numbers on the known list of base 2 and 3 palindromes easily fit in the memory of the Pico, it is reasonable to believe that the next one would fit as well. Therefore, the search for the 18th entry on that list could be a problem suitable for Pico@home and the consumption of energy similar to drinking a glass of water during the drought.
I'd gladly volunteer a dozen Picos to Pico@home. But that's for a different thread. It's actually feasible with the help of a Pi0/3/4, and who knows? A few hobbyist might play just for fun. A ton of technicalities there. Seems a fine way to make use of energy.
Do Pico's have any kind of serial number?

The search space is so large that a single unique seed could be used to parallelize the search for base 2, 3 palindromes across the entire Pico@home project--no network required. However, maybe there aren't any more base 2, 3 palindromes.
Here is an example of an almost base 2 and 3 palindrome:

Code: Select all

136055487118843303002161347910859263666511043
        120120212222121022121120102000001021121112022010220211121120100000201021121220121222212021021
        110000110011101011100100100001010100000100110000111000001111100110001000010100100111101101100000101000011001000000000100100011000110101110011000011
The binary representation is off by 11 digits. Is there a way to patch them?

ejolson
Posts: 8613
Joined: Tue Mar 18, 2014 11:47 am

Re: Double base palindromes

Mon Sep 27, 2021 12:36 am

ejolson wrote:
Mon Sep 27, 2021 12:10 am
ejolson wrote:
Sun Sep 26, 2021 7:40 pm
lurk101 wrote:
Sun Sep 26, 2021 6:22 pm

I'd gladly volunteer a dozen Picos to Pico@home. But that's for a different thread. It's actually feasible with the help of a Pi0/3/4, and who knows? A few hobbyist might play just for fun. A ton of technicalities there. Seems a fine way to make use of energy.
Do Pico's have any kind of serial number?

The search space is so large that a single unique seed could be used to parallelize the search for base 2, 3 palindromes across the entire Pico@home project--no network required. However, maybe there aren't any more base 2, 3 palindromes.
Here is an example of an almost base 2 and 3 palindrome:

Code: Select all

136055487118843303002161347910859263666511043
        120120212222121022121120102000001021121112022010220211121120100000201021121220121222212021021
        110000110011101011100100100001010100000100110000111000001111100110001000010100100111101101100000101000011001000000000100100011000110101110011000011
The binary representation is off by 11 digits. Is there a way to patch them?
It seems the question
    problem2.png
    problem2.png (23.51 KiB) Viewed 604 times
    https://arxiv.org/pdf/1403.0787.pdf

    was asked by Bérczes and Ziegler in 2014.

    While that was before the Raspberry Pico made searching for dual-base palindromes easy, maybe there are only 17 such numbers and an 18th will never be found.

    Return to “General”