Project Euler with Befunge


Fork me on GitHub
2014-09-23

Problem 036: Double-base palindromes

Description:

The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)


Solution:
v
0             v                      \<     v            *2\<     >:.55+,\   v
>093194*+**>::>55+*10p:55+%10g+\55+/:#^_$::0>10p:2%10g+\2/:#^_$-!#^_$        v
           |:-1                                                              <
v          <     v                      \<     v            *2\<     >:.55+,\v
>93194*+**>::55+/>55+*10p:55+%10g+\55+/:#^_$::0>10p:2%10g+\2/:#^_$-!#^_$     v
          |:-1                                                               <
          >"= ",,>+\:#<_+.@
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

The trick here is that we only need to test 1998 numbers. Because there are only so much base10 palindromes:

  • The numbers from 1 to 999 mirrored result into to palindromes 11 to 999999
  • The numbers from 1 to 999 mirrored at the last digit result into to palindromes 1 to 99999

Then we only need to test these numbers whether they are also binary palindromes.


Interpreter steps: 969 574
Execution time (BefunExec): 172ms (5.64 MHz)
Program size: 78 x 8 (fully conform befunge-93)
Solution: 872187
Solved at: 2014-09-23



made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript