Re: compound symmetrical primes
- To: mathgroup at smc.vnet.net
- Subject: [mg66513] Re: [mg66482] compound symmetrical primes
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Wed, 17 May 2006 03:30:34 -0400 (EDT)
- References: <200605160349.XAA01092@smc.vnet.net> <1D563537-7606-49E1-B34E-36C79575FEF1@mimuw.edu.pl>
- Sender: owner-wri-mathgroup at wolfram.com
On 16 May 2006, at 19:33, Andrzej Kozlowski wrote:
>
> On 16 May 2006, at 12:49, János wrote:
>
>> Let's say that a prime is symmetrical if prime==FromDigits[Reverse
>> [IntegerDigits[prime]]].
>>
>> I would say a prime is compound if two contiguous distinct subsets of
>> its digits are summing up to the same number. For example 211 is a
>> compound prime because 2=1+1. Similarly 15877 is a compound prime
>> because 1+5+8=7+7. May be there is a better definition in the prime
>> literature. The two distinct subset has to cover all the digits.
>>
>> Here is a little program that that looks for symmetrical compound
>> primes up to an mx limit.
>>
>> In[14]:=
>> lst = Timing[First[
>> Last[Reap[i = 1;
>> mx = 10^6; While[
>> i <= mx,
>> pr = Prime[i];
>> If[pr != FromDigits[
>> Reverse[
>> IntegerDigits[
>> pr]]], i++;
>> Continue[]; ];
>> prdig =
>> IntegerDigits[pr];
>> prlen = Length[
>> prdig]; j = 1;
>> While[j < prlen,
>> prLeft = Take[
>> prdig, {1, j}];
>> prRight = Take[
>> prdig, {j + 1,
>> prlen}];
>> If[Total[prLeft] !=
>> Total[prRight],
>> j++; Continue[],
>> Sow[pr]; Break[
>> ]]; ]; i++; ]; ]]]]
>> Out[14]=
>> {31.687534999999997*Second,
>> {11, 101, 16061, 31013,
>> 35053, 38083, 73037,
>> 74047, 91019, 94049,
>> 1120211, 1150511, 1160611,
>> 1180811, 1190911, 1250521,
>> 1280821, 1300031, 1360631,
>> 1390931, 1490941, 1520251,
>> 1550551, 1580851, 1600061,
>> 1630361, 1640461, 1660661,
>> 1670761, 1730371, 1820281,
>> 1880881, 1930391, 1970791,
>> 3140413, 3160613, 3260623,
>> 3310133, 3380833, 3400043,
>> 3460643, 3470743, 3590953,
>> 3670763, 3680863, 3970793,
>> 7100017, 7190917, 7250527,
>> 7300037, 7310137, 7540457,
>> 7600067, 7630367, 7690967,
>> 7750577, 7820287, 7850587,
>> 7930397, 7960697, 9110119,
>> 9200029, 9230329, 9280829,
>> 9320239, 9400049, 9440449,
>> 9470749, 9610169, 9620269,
>> 9650569, 9670769, 9700079,
>> 9770779, 9820289, 9980899}}
>>
>> Here are a few questions:
>>
>> Is there any compound symmetrical prime other than 11 whose length is
>> even ?
>>
>> Is there any compound symmetrical prime where the middle digit is not
>> zero ?
>>
>> Is there a much faster algorithm to find these numbers ? /I am
>> mostly procedural here :) because I could not find a functional check
>> for compoundness. /
>> I searched up to mx=10^8 and on my little iBook it took the whole
>> night.
>>
>> Let's say a number is periodical if it is a repetition of a subset of
>> its digits . For example 11 and 232323 are periodic numbers.
>>
>> Is 11 the only periodical symmetrical compound prime ?
>>
>> Thanks ahead,
>>
>> János
>>
>
>
> Consider a symmetrical number with an even number of digits. NTake
> the alternating sum of the digits e.g. if the number is abccba it
> will be a-b+c-c+b-a =0. In fact you always get zero. But an integer
> with this property must be divisible by 11, and hence unless it is
> 11 itself it won't be prime. This answers your first question.
>
> The second question: consider any symmetric and compound number
> with an odd number of digits. Let a will be its middle digit. The
> sums of the numbers to the left of a and to the right of will be
> equal, so unless a is 0, the number can't satisfy your definition
> of compoundedness (because if you add a non-zero number to one of
> two numbers that are equal, the resulting two numbers won't be
> equal any more. That is what non-zero means ;-)).
>
> The question about primes that are periodic and symmetric is
> harder, but I think I can also show that the only one is 11. The
> proof again reduces to the same divisibility by 11 criterion as
> above. We use the fact that the middle number is 0. You write out
> the various ways in which a periodic number can be formed, and then
> use the fact that the first digit is the same as the last, the
> second the same as the last but one etc. Finally you take the
> alternating sum of digits and, I think, that will always come to 0.
>
> Once one has answered your first two questions it is easy to
> construct a much faster code. Here is an example. One can make it
> much nicer, but I will leave that to others.
>
>
> ls=Last[Last[n=
> 1;Reap[While[n<
> 10^4,If[PrimeQ[x=FromDigits[Join[IntegerDigits[n], {0},
> Reverse[
> IntegerDigits[n]]]]],Sow[x]];n++]]]];//Timing
>
>
> {0.650904 Second,Null}
>
>
> Length[ls]
>
>
> 526
>
>
> Take[ls,20]
>
>
> {101,16061,31013,35053,38083,73037,74047,91019,94049,1120211,1150511,1
> 160611,
> 1180811,1190911,1250521,1280821,1300031,1360631,1390931,1490941}
>
> Note that the code does not construct the first number 11, which we
> know is rather "special".
>
> One could also try to make use of the fact that there is no need to
> consider those n whose first digit is 2 or 5, since that first
> digit will be the last digit of the symmetric number which we are
> constructing and numbers ending with 2 or 5 can't be prime.
> However, trying to make use of this in the code might make it more
> complex and may not result in any improved efficiency.
>
> Andrzej Kozlowski
> Tokyo, Japan
>
I got curious about this last point (I should have written that we
need not consider not just the numbers whose first digit is 2 but
whose first digit is odd, of course). So I tried to compare these two
codes:
In[4]:=
Timing[ls1 = Last[Last[n = 1; Reap[While[n < 10^5, If[PrimeQ[x =
FromDigits[Join[IntegerDigits[n], {0}, Reverse[IntegerDigits[n]]]]],
Sow[x]]; n++]]]]; ]
Out[4]=
{9.066753000000002*Second, Null}
In[5]:=
Timing[
ls2 = Last[Last[n = 1; Reap[While[n < 10^5, With[{p = IntegerDigits
[n]}, If[OddQ[First[p]] && First[p] != 5 &&
PrimeQ[x = FromDigits[Join[p, {0}, Reverse[p]]]], Sow
[x]]]; n++]]]]; ]
Out[5]=
{8.808506999999999*Second, Null}
In[7]:=
ls1==ls2
Out[7]=
True
and the second is only slightly faster for this order of magnitude. I
guess, this is not really surprising, although I think the difference
should grow as we make longer and longer sequences. The second code
avoids a lot of PrimeQ tests, at the expense of checking the testing
the first digit for oddness and non-divisibility by 5. PrimeQ is,
however, extremely fast, though in theory, for extremely large
numbers it could produce a false positive. If we used instead a
certified primality test the above results would surely be very
different.
Still, it should be possible to improve the above code by using as
"building blocks" only numbers wit
Andrzej Kozlowski
- References:
- compound symmetrical primes
- From: János <janos.lobb@yale.edu>
- compound symmetrical primes