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