Prime permutations
Problem 049: Prime permutations
The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways:
- (i) each of the three terms are prime, and,
- (ii) each of the 4-digit numbers are permutations of one another.
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.
What 12-digit number do you form by concatenating the three terms in this sequence?
Solution:
" :v55:/+55\+2%+5<\ v<*2v+55\+2%+<:v>$:.48*,"Z%"*+:.48*,"Z%"*+. @
( :>+%2+\55+/2+***^ 01+%/>* -#v_-!|:|< #
% v5:/+55\+2%+55::g<:1+2* v <">::2%!#v_v >10g\%!#v_:10g2/`|
" >5+%2+\55+/:55v p05+* $ ve#< v%3:>#<#^ #< > v :
* +v***+2/+55\+2%+< ^<5>^ $ c` > !#^_10p7:^:+6_^#%\g01-2<
7 1>\"Z%"*+:55+%2+\55+/:^ v <"*^ $$$<
>+^ < >^
Explanation:
This could be the first problem with prime numbers but without a prime sieve.
We iterate through the numbers from 1488 to 3340 and search for palindromes.
To speed up the palindrome calculation we calculate the product of each digit plus two and compare the product of our three numbers.
This is only an approximation, but a rather good one. In tested the numbers from 0 to 100 000 and there were zero failures.
So now we've got the numbers where digit_product(p) == digit_product(p+3330) == digit_product(p+6660) (in fact there are only 40 of these).
We then use a simple primality test to check if all three numbers are prime.
The primality test is basically a port of the wikipedia version to befunge. Wit it we only have to do n/6 divisions to test a number n for primality.
All in all tis leads to a fast, small and not very grid-intensive program (Only one field is used, and only as a temporary storage to swap three values).
| Interpreter steps: | 378 809 |
| Execution time (BefunExec): | 124ms (3.05 MHz) |
| Program size: | 66 x 8 (fully conform befunge-93) |
| Solution: | 296962999629 |
| Solved at: | 2015-01-09 |