MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: RE: Re: Re: level curve selection
  • Next by Date: Re: Re: Re: Re: )
  • Previous by thread: Re: compound symmetrical primes
  • Next by thread: Re: compound symmetrical primes