Re: compound symmetrical primes
- To: mathgroup at smc.vnet.net
- Subject: [mg66522] Re: compound symmetrical primes
- From: Jean-Marc Gulliet <jeanmarc.gulliet at gmail.com>
- Date: Wed, 17 May 2006 03:31:13 -0400 (EDT)
- Organization: The Open University, Milton Keynes, UK
- References: <e4birv$1a5$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
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.
> [...]
> Is there any compound symmetrical prime where the middle digit is not
> zero ?
No. We can use a proof by contradiction. Indeed the result is even
stronger since we can show that any compound symmetrical positive
integer - not just prime -- of odd length must have its middle digit
equal to zero.
Here is an outline of the proof.
Let n be an arbitrary compound symmetrical positive integer of odd
length with its middle digit d[k] != 0.
n can be written as d[1]d[2]...d[k-1]d[k]d[k-1]...d[2]d[1] (for
instance, say that n=1234321, then d[1]=1, d[2]=2, d[k-1]=3, d[k]=4)
since n is symmetrical.
We have the sum of the first (k-1)-th digits must be equal to the sum of
the last (k-1)-th digits. That is d[1]+d[2]+...+d[k-1]==d[k-1]+...+d[2]+d[1]
Since n is compound, we have either
d[1]+d[2]+...+d[k-1]+d[k]==d[k-1]+...+d[2]+d[1]
or d[k-1]+...+d[2]+d[1]+d[k]==d[1]+d[2]+...+d[k-1]
Either one leads to
(d[1]-d[1])+(d[2]-d[2])+...+(d[k-1]-d[k-1])==d[k], d[k]!=0 by assumption
that is 0==d[k]!=0 which is a contradiction.
Therefore d[k] must be zero.
I hope I have not been to confusing!
> 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.
I have just done some improvements (see In[1]) on your original
procedural code {In[3]) and the execution speed is improved by a factor
two at least:
In[1]:=
lst=Timing[
Module[
{i=1,mx=10^4,prdig,prlen,j},First[Last[Reap[
While[iâ?¤mx,
prdig=IntegerDigits[Prime[i]];
If[prdig==Reverse[prdig],
prlen=Length[prdig];
j=1;
While[j<prlen,
If[Tr[Part[prdig,
Range[1,j]]]==Tr[Part[prdig,Range[j+1,prlen]]],
Sow[FromDigits[prdig]];Break[],
j++;
];
];
];
i++;
];
]]]]]
Length[lst[[2]]]
Out[1]=
{0.109 Second,{11,101,16061,31013,35053,38083,73037,74047,91019,94049}}
Out[2]=
10
In[3]:=
lst = Timing[First[Last[Reap[i = 1; mx = 10^4;
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++; ]; ]]]]
Length[lst[[2]]]
Out[3]=
{0.219 Second,{11,101,16061,31013,35053,38083,73037,74047,91019,94049}}
Out[4]=
10
I am sure that other things can be improved; unfortunately, I have not
had the time to look for a genuine functional program.
Best regards,
Jean-Marc