Project Euler with Befunge


Fork me on GitHub
2014-12-11

Problem 046: Goldbach's other conjecture

Description:

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2 * 1^2
15 = 7 + 2 * 2^2
21 = 3 + 2 * 3^2
25 = 7 + 2 * 3^2
27 = 19 + 2 * 2^2
33 = 31 + 2 * 1^2

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?


Solution:
v
# ... #
. . . .
.  .  .
. . . .
# ... #
                                                                                                                            >2                               v           >0v>vv p09+g09*2:p07-\g07+g09:<
                                                                                             v           p+1/g01\%g01:\"O"< $v                               <           9@pp8# v/4    <   >:90g+70g`! |
>"d"2*:10p"2":20p*40p230pv                                     >030p 350p                    >50g2+:50p::10g%\10g/1+g" "-#^_^>1+:50g-!#v_::10g%\10g/1+g" "-!#^_:50g\-2/:0^.70>0g>:70g`#^_>:|:/4p09/2g09<
vp08*8**::**::8p11p10:" "<                                    _^#`g03g04<                    ^                                         >                                  ^>^ >90g2/90p4/^ >$90g:*-#v_v
>"X"30g:10g%\10g/1+p30g>30g+:40g\`       #v_$>30g1+:30p:10g%\10g/1+g" "-|                    $                               ^                                                                      <
                       ^p+1/g01\%g01:\" ":<  ^                          <                    ^                                                                                                        <
This program is too big to display/execute here, click [download] to get the full program.

Explanation:

I really missed my sieve of erastothenes. There were really a few problems without primes in a row.

In this problem we go through all primes i, search through all smaller primes j were (i-j)/2 is a quadratic number. If you can't find one, this falsifies the theorem.

Also we use the code from problem 46 to calculate the integer square root.


Interpreter steps: 77 542 913
Execution time (BefunExec): 13s (5.58 MHz)
Program size: 200 x 57
Solution: 5777
Solved at: 2014-12-11



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