Re: Re: SuperPrimes
- To: mathgroup at christensen.cybernetics.net
- Subject: [mg666] Re: [mg634] Re: [mg622] SuperPrimes
- From: villegas (Robert Villegas)
- Date: Sat, 8 Apr 1995 02:58:52 -0500
> What about repus prime rib, for all those left-handed butchers out here?
> (Eg: 7, 907, and 6907 are prime, so 6907 is in repusPrime[4].) This
> problem seems fundamentally harder. Here's the obvious slow method. Any
> one care to speed it up?
>
>
> In[4]:= repusPrimeQ[n_] := And @@
> Map[ PrimeQ[Mod[n,#]]&,10^Range[Length @ IntegerDigits[n]] ]
>
> In[5]:= repusPrime[n_] := Select[Range[10^(n-1),10^n-1],repusPrimeQ]
Lou,
I think you're right that it's fundamentally harder, or at least
slower in the long run, because at the nth step, you can always
add multiples of 10^n to *all* your previous numbers to get potential
new ones. The search space for the next step is proportional
(factor of 9) to the size of the current step, and to boot, PrimeQ
isn't speeding up as the order of magnitude grows, so the timing,
at least using our approach of generate 'em all and test 'em, is
probably very vaguely exponential (throwing a density estimation of
prime numbers in there and some timing estimate of PrimeQ could
help make that precise). Maybe some clever number theory could
improve this...?
Anyway, we can build them up in just about the same way you and I
did for the original problem, and at least for the first few steps it's
not too slow:
repusPrime[n_] :=
Fold[
Select[Flatten @ Outer[Plus, Range[9] 10^#2, #1], PrimeQ]&,
{2, 3, 5, 7}, Range[n - 1]
]
Or if you want to keep all the ones from previous steps (having 1-digit
through n-digit "repus" primes):
repusPrimeCumulative[n_] :=
Fold[
Join[#1, Select[Flatten @ Outer[Plus, Range[9] 10^#2, #1], PrimeQ]]&,
{2, 3, 5, 7}, Range[n - 1]
]
In[16]:= repusPrimeCumulative[3] //Short
Out[16]//Short=
> {2, 3, 5, 7, 13, 17, 23, 37, 43, 47, <<45>>, 947, 953, 967, 983, 997}
A quick (well, not all that quick) way to see how many have been
found up through the nth step is to replace the Fold with FoldList
in repusPrimeCumulative (that's the only change you need). This
gives you the intermediate stages in the build-up and you can just
count the number of elements:
repusPrimeCumulativeLists[n_] :=
FoldList[
Join[#1, Select[Flatten @ Outer[Plus, Range[9] 10^#2, #1], PrimeQ]]&,
{2, 3, 5, 7}, Range[n - 1]
]
In[16]:= Length /@ repusPrimeCumulativeLists[8]
Out[16]= {4, 15, 60, 208, 625, 1672, 3984, 8779}
It would be interesting to see a really fast way to construct the
ambidextrous butcher's prime ribs.
Robby Villegas