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