Prime digit replacements
Problem 051: Prime digit replacements
By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values:13, 23, 43, 53, 73, and 83, are all prime.
By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.
Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.
Solution:
############## >#|v#-*8"}"g20< $ ^ < >1#0|
OOO OO OOO # ^ @# ># ^# < < <^_^#<1>v
############## >22g1+:22p3-!^2#
110001#??????# > ^ <
101001#??????# > ^v24 pg21+7\+"0"%+55g24:>#<: !#v_ v g+
100101#??????# >g55+/42p> ^ |-"0"gg21: -1<p24g206 <
100011#??????# ^pg21+7\+"0"g22:< #>#$>1-:7+12gvgg
011001#??????# >82g8-| @ ^6<|:\-"0"g <"2
010101#??????# $ >72g.^ >$ ^>$#<55+*+55+v02
010011#??????# vp29g22p281 $_v# `/2g25:_^#%\g25< v_v# %2: <v*+55+*+55+*<"-
001101#??????# $ : >^ ># ^#>#<:3%v >+55+*+v >^
001011#??????# $ >2-52g\%!#^_6+:^:7p25_^# < ^ p27:<
000111#??????# >92g1+92pv v_v# :>#<:42g55+%"0"+\7+92g4+p42 v
############## |-9g29< >602g42p>1 -:12gg"0"-| ^ <p24/+55g<
> ^ ^ $< v6$< >:92g"0"+\7+92g4+p^
v_v# `/2g25:_v# %\g25< v_v# %2<>>1-:7+92g4v>v
8 v ># ^#>#<:3%v: |:\-"0"g+ <+5
2 >:2-52g\%!#v_6+:^:7p25_^# <+ >$55+*+55+*^5
>g1+82p >$ ^ ^ *+55+*+55+*+<
Explanation:
This is effectively an optimized implementation of this algorithm.
You can see the ten patterns on the left side and beside them the area were we build our numbers.
So what we do is iterate through the numbers from 100 to 1 000, through the ten patterns and through the digits 0, 1 and 2.
In each iteration we generate the number (from value, pattern and digit) and test for it primeness (with a simple primality test - no prime sieve).
If we found a prime we count the number of primes in it's family and if this count is eight we print the generated number and exit.
This program is not the fastest, because I check all the primes "manually" and not with an prime sieve each iteration takes quite a time. But I wanted this to fit into the befunge-93 size restrictions, and even without a sieve the execution time is OK - for a befunge program.
| Interpreter steps: | 802 550 671 |
| Execution time (BefunExec): | 1min 53s (7.05 MHz) |
| Program size: | 78 x 20 (fully conform befunge-93) |
| Solution: | 121313 |
| Solved at: | 2015-01-17 |