## Sphenic tree by factor concatenation on 114

Expand Messages
• Dear primenumbers group members, I am attempting to solve a problem with PARI/GP that is probably not amenable to it. Better would be something running truly
Message 1 of 16 , Jun 11, 2011
• 0 Attachment
I am attempting to solve a problem with PARI/GP that is probably not amenable to it. Better would be something running truly as a parallel programming task. The problem can possibly be deciphered from the subject line, but I should explain.
Until 114, the sphenic numbers lead to one other sphenic number by concatenating prime factors in two cases and none in the others. 114 produces a tree of sphenics numbering at least in the millions. After a couple of weeks, the single line of processing has produced over 1.5 million with 38 42-digit nodes. While the number of immediate descendant nodes per node is apt to go below 1 on this single line, it hasn't yet. And each node researched is also taking longer, of course. If anyone would like to take up this, what I think is an interesting, challenge, there is no way for me to do it unless I am given advice contradicting my belief no properly parallel method will work in this language.
Jim Merickel

Sent from my Motorola ATRIXâ„˘ 4G on AT&T

[Non-text portions of this message have been removed]
• ... Here are the counts for the first 21 iterations: {sp(n)=local(f=factor(n)); if(#f[,1]==3&&sum(j=1,3,f[j,2])==3,f[,1]~,0);}
Message 2 of 16 , Jun 12, 2011
• 0 Attachment
"James Merickel" <merk7777777@...> wrote:

> After a couple of weeks, the single line of processing
> has produced over 1.5 million ...

Here are the counts for the first 21 iterations:

{sp(n)=local(f=factor(n));
if(#f[,1]==3&&sum(j=1,3,f[j,2])==3,f[,1]~,0);}

{spp(s)=local(pk,v=[],t);for(k=1,6,pk=perm[k];t="";
for(j=1,3,t=concat(t,s[pk[j]]));t=sp(eval(t));
if(t,v=concat(v,[t])));v;}

perm=[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]];
v=spp(sp(114));iter=21;

{for(i=2,iter,u=[];print1(#v" ");for(k=1,#v,
u=concat(u,spp(v[k])));v=u);print(#v);}

2 2 2 1 3 7 13 28 39 73 141 264 459 757 1220 1937 3054 4700 7173 10766 15803

> there is no way for me to do it unless I am given advice
> contradicting my belief no properly parallel method will
> work in this language

If you have N processors, simply split
up these 15803 daughters between them and
let each processor operate independently.

David
• Let me guess why it s called embarrassing . I had thought of something essentially the same but quite a bit harder to program (for me anyway, using saves and
Message 3 of 16 , Jun 12, 2011
• 0 Attachment
Let me guess why it's called 'embarrassing'. I had thought of something essentially the same but quite a bit harder to program (for me anyway, using saves and calls) since the original post. Anyway, thanks for what seems like it should have been obvious to me, David.

On Sun Jun 12th, 2011 4:42 AM EDT djbroadhurst wrote:

>
>
>"James Merickel" <merk7777777@...> wrote:
>
>> After a couple of weeks, the single line of processing
>> has produced over 1.5 million ...
>
>Here are the counts for the first 21 iterations:
>
>{sp(n)=local(f=factor(n));
>if(#f[,1]==3&&sum(j=1,3,f[j,2])==3,f[,1]~,0);}
>
>{spp(s)=local(pk,v=[],t);for(k=1,6,pk=perm[k];t="";
>for(j=1,3,t=concat(t,s[pk[j]]));t=sp(eval(t));
>if(t,v=concat(v,[t])));v;}
>
>perm=[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]];
>v=spp(sp(114));iter=21;
>
>{for(i=2,iter,u=[];print1(#v" ");for(k=1,#v,
>u=concat(u,spp(v[k])));v=u);print(#v);}
>
>2 2 2 1 3 7 13 28 39 73 141 264 459 757 1220 1937 3054 4700 7173 10766 15803
>
>> there is no way for me to do it unless I am given advice
>> contradicting my belief no properly parallel method will
>> work in this language
>
>If you have N processors, simply split
>up these 15803 daughters between them and
>let each processor operate independently.
>
>David
>
• ... http://en.wikipedia.org/wiki/Embarrassingly_parallel David
Message 4 of 16 , Jun 12, 2011
• 0 Attachment
James Merickel <merk7777777@...> wrote:

> Let me guess why it's called 'embarrassing'.

http://en.wikipedia.org/wiki/Embarrassingly_parallel

David
• ... If my client-server method did not screw up, the sequence of counts continues 23366 33947 48816 69547 97473 135489 186328 252326 338513 448911 589071 Might
Message 5 of 16 , Jun 12, 2011
• 0 Attachment

> Here are the counts for the first 21 iterations:
> 2 2 2 1 3 7 13 28 39 73 141 264 459 757
> 1220 1937 3054 4700 7173 10766 15803

If my client-server method did not screw up,
the sequence of counts continues

23366 33947 48816 69547 97473 135489
186328 252326 338513 448911 589071

Might James confirm this, from his single-processor data?

David
• ... Here are my counts for the first 37 iterations: 2, 2, 2, 1, 3, 7, 13, 28, 39, 73, 141, 264, 459, 757, 1220, 1937, 3054, 4700, 7173, 10766, 15803, 23366,
Message 6 of 16 , Jun 13, 2011
• 0 Attachment

> 186328 252326 338513 448911 589071

Here are my counts for the first 37 iterations:

2, 2, 2, 1, 3, 7, 13, 28, 39, 73, 141, 264, 459,
757, 1220, 1937, 3054, 4700, 7173, 10766, 15803,
23366, 33947, 48816, 69547, 97473, 135489,
186328, 252326, 338513, 448911, 589071,
766390, 984903, 1253696, 1578502, 1966106,

with ratios of successive counts, from the last 10 entries,
1.354, 1.342, 1.326, 1.312, 1.301, 1.285, 1.273, 1.259, 1.246,
indicating that we are still well below the shrinking point.

It is clear that James was very generous in allowing
6 possible decimal concatenations of the 3 distinct
prime factors of a sphenic number.

David
• Yes, suspected my one computer was not adequate in any case. I would have had to do some hands-on measurements to be sure, and probably would not have. So I
Message 7 of 16 , Jun 13, 2011
• 0 Attachment
Yes, suspected my one computer was not adequate in any case. I would have had to do some hands-on measurements to be sure, and probably would not have. So I am glad for this particular response. My one PARI/GP window is done without the dividing line between iterations and has just the first 1.696Million nodes so far (with four 43-digit numbers and current mode at 33 digits with just over 230000).

On Mon Jun 13th, 2011 6:34 PM EDT djbroadhurst wrote:

>
>
>
>> 186328 252326 338513 448911 589071
>
>Here are my counts for the first 37 iterations:
>
>2, 2, 2, 1, 3, 7, 13, 28, 39, 73, 141, 264, 459,
>757, 1220, 1937, 3054, 4700, 7173, 10766, 15803,
>23366, 33947, 48816, 69547, 97473, 135489,
>186328, 252326, 338513, 448911, 589071,
>766390, 984903, 1253696, 1578502, 1966106,
>
>with ratios of successive counts, from the last 10 entries,
>1.354, 1.342, 1.326, 1.312, 1.301, 1.285, 1.273, 1.259, 1.246,
>indicating that we are still well below the shrinking point.
>
>It is clear that James was very generous in allowing
>6 possible decimal concatenations of the 3 distinct
>prime factors of a sphenic number.
>
>David
>
• Definition: A number is sphenic iff it is the product of 3 distinct primes. A sphenic chain is a sequence of sphenic numbers such that each except the first
Message 8 of 16 , Jun 14, 2011
• 0 Attachment
Definition: A number is sphenic iff it is the product of 3
distinct primes. A "sphenic chain" is a sequence of sphenic
numbers such that each except the first is one of the 6
decimal concatenations of the primes dividing its predecessor.

Example: Here is a chain of length 10:
1: 114 = 3*2*19
2: 3219 = 37*29*3
3: 37293 = 401*31*3
4: 401313 = 11*3*12161
5: 11312161 = 7*53*30491
6: 75330491 = 2887*97*269
7: 288797269 = 23*187409*67
8: 2318740967 = 1097*61*34651
9: 10976134651 = 1163*229*41213
10: 116322941213 [one may continue this chain]
which we may conveniently denote by
[114, 3, 6, 6, 3, 1, 5, 2, 3, 3]
where 114 is the first number and then we indicate which of
the permutations {123, 132, 213, 231, 312, 321} were used.

Here is how generate a chain of length 80, using Pari-GP:

{sphen80 = [114,
3, 6, 6, 3, 1, 5, 2, 3, 3, 4, 5, 3, 5, 5, 6, 3, 6, 3, 1, 3,
3, 4, 5, 3, 4, 4, 6, 3, 1, 1, 1, 1, 2, 1, 1, 5, 6, 6, 2, 5,
2, 2, 6, 3, 3, 1, 4, 1, 5, 3, 6, 3, 5, 4, 3, 2, 6, 5, 2, 4,
3, 2, 3, 5, 3, 4, 6, 1, 1, 3, 5, 2, 6, 4, 4, 3, 1, 6, 2];}

{ischain(s)=local(f,n=s[1],P,t);
P=[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]];
for(k=1,#s,print1(k": ");n=eval(n);f=factor(n)[,1];
if(n!=f[1]*f[2]*f[3],print("fail");break,
if(k==#s,print(n" has factors "f~),print1(n " = ");
n="";for(j=1,3,t=f[P[s[k+1]][j]];print1(t);
if(j<3,print1("*"),print());n=concat(n,t)))));}

ischain(sphen80);

with takes less than a minute to generate the output in
Sadly, none of the 6 concatenations the 3 primes
from the 80th member yields a sphenic number.

Puzzle: Find a sphenic chain with more than 80 members.

economical format that I used for "sphen80".

• Hello David, ... Many GHz hours later..... {sphen81 = [114, 3, 6, 6, 3, 2, 2, 4, 4, 3, 4, 3, 6, 2, 2, 1, 1, 3, 4, 2, 6, 6, 4, 2, 6, 2, 2, 4, 4, 3, 2, 1, 3, 5,
Message 9 of 16 , Jun 15, 2011
• 0 Attachment
Hello David,

At 03:19 AM 15/06/2011, djbroadhurst wrote:

>Definition: A number is sphenic iff it is the product of 3
>distinct primes. A "sphenic chain" is a sequence of sphenic
>numbers such that each except the first is one of the 6
>decimal concatenations of the primes dividing its predecessor.
>
>[ snip ]
>Here is how generate a chain of length 80, using Pari-GP:
>
> {sphen80 = [114,
> 3, 6, 6, 3, 1, 5, 2, 3, 3, 4, 5, 3, 5, 5, 6, 3, 6, 3, 1, 3,
> 3, 4, 5, 3, 4, 4, 6, 3, 1, 1, 1, 1, 2, 1, 1, 5, 6, 6, 2, 5,
> 2, 2, 6, 3, 3, 1, 4, 1, 5, 3, 6, 3, 5, 4, 3, 2, 6, 5, 2, 4,
> 3, 2, 3, 5, 3, 4, 6, 1, 1, 3, 5, 2, 6, 4, 4, 3, 1, 6, 2];}
>
>[ snip]
>Puzzle: Find a sphenic chain with more than 80 members.

Many GHz hours later.....

{sphen81 = [114,
3, 6, 6, 3, 2, 2, 4, 4, 3, 4, 3, 6, 2, 2, 1, 1, 3, 4, 2, 6,
6, 4, 2, 6, 2, 2, 4, 4, 3, 2, 1, 3, 5, 6, 2, 4, 5, 5, 1, 4,
6, 4, 6, 4, 5, 1, 3, 1, 1, 1, 4, 1, 1, 4, 3, 4, 2, 3, 4, 2,
3, 2, 1, 5, 4, 5, 6, 3, 5, 6, 3, 5, 6, 6, 3, 4, 4, 2, 4, 4];}

Best Regards,

Kevin.

[Non-text portions of this message have been removed]
• ... And then of course, just a few minutes later: {sphen84a = [114, 3, 6, 6, 3, 2, 2, 4, 4, 3, 4, 3, 6, 2, 2, 1, 1, 3, 4, 2, 6, 6, 4, 2, 6, 2, 2, 4, 4, 3, 2,
Message 10 of 16 , Jun 15, 2011
• 0 Attachment
At 08:09 PM 15/06/2011, Kevin Acres wrote:
>Hello David,
>
>At 03:19 AM 15/06/2011, djbroadhurst wrote:
>
> >Definition: A number is sphenic iff it is the product of 3
> >distinct primes. A "sphenic chain" is a sequence of sphenic
> >numbers such that each except the first is one of the 6
> >decimal concatenations of the primes dividing its predecessor.
> >
> >[ snip ]
> >Here is how generate a chain of length 80, using Pari-GP:
> >
> > {sphen80 = [114,
> > 3, 6, 6, 3, 1, 5, 2, 3, 3, 4, 5, 3, 5, 5, 6, 3, 6, 3, 1, 3,
> > 3, 4, 5, 3, 4, 4, 6, 3, 1, 1, 1, 1, 2, 1, 1, 5, 6, 6, 2, 5,
> > 2, 2, 6, 3, 3, 1, 4, 1, 5, 3, 6, 3, 5, 4, 3, 2, 6, 5, 2, 4,
> > 3, 2, 3, 5, 3, 4, 6, 1, 1, 3, 5, 2, 6, 4, 4, 3, 1, 6, 2];}
> >
> >[ snip]
> >Puzzle: Find a sphenic chain with more than 80 members.
>
>Many GHz hours later.....
>
> {sphen81 = [114,
> 3, 6, 6, 3, 2, 2, 4, 4, 3, 4, 3, 6, 2, 2, 1, 1, 3, 4, 2, 6,
> 6, 4, 2, 6, 2, 2, 4, 4, 3, 2, 1, 3, 5, 6, 2, 4, 5, 5, 1, 4,
> 6, 4, 6, 4, 5, 1, 3, 1, 1, 1, 4, 1, 1, 4, 3, 4, 2, 3, 4, 2,
> 3, 2, 1, 5, 4, 5, 6, 3, 5, 6, 3, 5, 6, 6, 3, 4, 4, 2, 4, 4];}

And then of course, just a few minutes later:

{sphen84a = [114,
3, 6, 6, 3, 2, 2, 4, 4, 3, 4, 3, 6, 2, 2, 1, 1, 3, 4, 2, 6,
6, 4, 2, 6, 2, 2, 4, 4, 3, 2, 1, 3, 5, 6, 2, 4, 5, 5, 1, 4,
6, 4, 6, 4, 5, 1, 3, 1, 1, 1, 4, 1, 1, 4, 3, 4, 2, 3, 4, 2,
3, 2, 1, 5, 4, 5, 6, 3, 5, 6, 3, 5, 6, 6, 3, 4, 4, 2, 4, 4,
4, 3, 4];}

{sphen84b = [114,
3, 6, 6, 3, 2, 2, 4, 4, 3, 4, 3, 6, 2, 2, 1, 1, 3, 4, 2, 6,
6, 4, 2, 6, 2, 2, 4, 4, 3, 2, 1, 3, 5, 6, 2, 4, 5, 5, 1, 4,
6, 4, 6, 4, 5, 1, 3, 1, 1, 1, 4, 1, 1, 4, 3, 4, 2, 3, 4, 2,
3, 2, 1, 5, 4, 5, 6, 3, 5, 6, 3, 5, 6, 6, 3, 4, 4, 2, 4, 4,
4, 3, 3];}

[Non-text portions of this message have been removed]
• ... Congrats! I m now in the low 90s, but do not expect to make it to length 100. David
Message 11 of 16 , Jun 15, 2011
• 0 Attachment
Kevin Acres <research@...> wrote:

> {sphen84a = [114,
> 3, 6, 6, 3, 2, 2, 4, 4, 3, 4, 3, 6, 2, 2, 1, 1, 3, 4, 2, 6,
> 6, 4, 2, 6, 2, 2, 4, 4, 3, 2, 1, 3, 5, 6, 2, 4, 5, 5, 1, 4,
> 6, 4, 6, 4, 5, 1, 3, 1, 1, 1, 4, 1, 1, 4, 3, 4, 2, 3, 4, 2,
> 3, 2, 1, 5, 4, 5, 6, 3, 5, 6, 3, 5, 6, 6, 3, 4, 4, 2, 4, 4,
> 4, 3, 4];}
>
> {sphen84b = [114,
> 3, 6, 6, 3, 2, 2, 4, 4, 3, 4, 3, 6, 2, 2, 1, 1, 3, 4, 2, 6,
> 6, 4, 2, 6, 2, 2, 4, 4, 3, 2, 1, 3, 5, 6, 2, 4, 5, 5, 1, 4,
> 6, 4, 6, 4, 5, 1, 3, 1, 1, 1, 4, 1, 1, 4, 3, 4, 2, 3, 4, 2,
> 3, 2, 1, 5, 4, 5, 6, 3, 5, 6, 3, 5, 6, 6, 3, 4, 4, 2, 4, 4,
> 4, 3, 3];}

Congrats!

I'm now in the low 90s, but do not expect to make it to length 100.

David
• ... In fact, I was able to reach length 105: {sphen105 = [114, 3, 6, 6, 3, 2, 2, 4, 4, 3, 4, 1, 6, 1, 4, 1, 3, 2, 3, 2, 6, 1, 6, 3, 5, 5, 6, 2, 1, 6, 6, 6, 1,
Message 12 of 16 , Jun 15, 2011
• 0 Attachment

> do not expect to make it to length 100

In fact, I was able to reach length 105:

{sphen105 = [114,
3, 6, 6, 3, 2, 2, 4, 4, 3, 4, 1, 6, 1, 4, 1, 3, 2, 3, 2, 6,
1, 6, 3, 5, 5, 6, 2, 1, 6, 6, 6, 1, 2, 5, 4, 3, 5, 2, 5, 2,
4, 1, 5, 1, 6, 5, 3, 3, 5, 5, 2, 1, 5, 5, 1, 6, 4, 5, 5, 3,
5, 2, 4, 4, 4, 3, 4, 5, 6, 4, 6, 3, 6, 4, 2, 4, 5, 2, 6, 1,
1, 4, 6, 1, 6, 1, 2, 3, 2, 4, 6, 3, 3, 1, 6, 3, 3, 3, 1, 3,
1, 5, 3, 1];}

contains 8 helpers, obtained by ECM, and then the chain of
is generated in less than 4 minutes.

David
• ... The best I can do at present is length 108: {sphen108 = [114, 3, 6, 6, 3, 2, 2, 4, 4, 3, 4, 1, 6, 1, 4, 1, 3, 2, 3, 2, 6, 1, 6, 3, 5, 5, 6, 2, 1, 6, 6, 6,
Message 13 of 16 , Jun 16, 2011
• 0 Attachment

> able to reach length 105

The best I can do at present is length 108:

{sphen108 = [114,
3, 6, 6, 3, 2, 2, 4, 4, 3, 4, 1, 6, 1, 4, 1, 3, 2, 3, 2, 6,
1, 6, 3, 5, 5, 6, 2, 1, 6, 6, 6, 1, 2, 5, 4, 3, 5, 2, 5, 2,
4, 1, 5, 1, 6, 5, 3, 3, 5, 5, 2, 1, 5, 5, 1, 6, 4, 5, 5, 3,
5, 2, 4, 4, 4, 3, 4, 5, 6, 4, 6, 3, 6, 4, 2, 4, 5, 2, 6, 1,
1, 4, 6, 1, 6, 1, 2, 3, 2, 4, 6, 3, 3, 1, 6, 3, 3, 3, 1, 3,
5, 1, 4, 5, 2, 5, 2];}

with input and output in

David
• ... Length 109 is achieved by {sphen109 = [114, 3, 6, 6, 3, 2, 2, 4, 4, 3, 4, 1, 6, 1, 4, 1, 3, 2, 3, 2, 6, 1, 6, 3, 5, 5, 6, 2, 1, 6, 6, 6, 1, 2, 5, 4, 3, 5,
Message 14 of 16 , Jun 20, 2011
• 0 Attachment

> The best I can do at present is length 108

Length 109 is achieved by

{sphen109 = [114,
3, 6, 6, 3, 2, 2, 4, 4, 3, 4, 1, 6, 1, 4, 1, 3, 2, 3, 2, 6,
1, 6, 3, 5, 5, 6, 2, 1, 6, 6, 6, 1, 2, 5, 4, 3, 5, 2, 5, 2,
4, 1, 5, 1, 6, 5, 3, 3, 5, 5, 2, 1, 5, 5, 1, 6, 4, 5, 5, 3,
5, 2, 4, 4, 4, 3, 4, 5, 6, 4, 6, 5, 6, 2, 1, 1, 6, 6, 5, 6,
6, 4, 6, 6, 2, 4, 4, 6, 6, 2, 5, 3, 1, 2, 2, 1, 2, 2, 4, 3,
1, 4, 3, 1, 2, 5, 3, 5];}

with input and output in

David
• Hi David, ... Well done for that. Its been windy here and wind = power outage where I live :-) One day I ll get a decent size UPS. Best Regards, Kevin.
Message 15 of 16 , Jun 20, 2011
• 0 Attachment
Hi David,

At 02:20 PM 21/06/2011, djbroadhurst wrote:

>
> > The best I can do at present is length 108
>
>Length 109 is achieved by
>
> {sphen109 = [114,
> 3, 6, 6, 3, 2, 2, 4, 4, 3, 4, 1, 6, 1, 4, 1, 3, 2, 3, 2, 6,
> 1, 6, 3, 5, 5, 6, 2, 1, 6, 6, 6, 1, 2, 5, 4, 3, 5, 2, 5, 2,
> 4, 1, 5, 1, 6, 5, 3, 3, 5, 5, 2, 1, 5, 5, 1, 6, 4, 5, 5, 3,
> 5, 2, 4, 4, 4, 3, 4, 5, 6, 4, 6, 5, 6, 2, 1, 1, 6, 6, 5, 6,
> 6, 4, 6, 6, 2, 4, 4, 6, 6, 2, 5, 3, 1, 2, 2, 1, 2, 2, 4, 3,
> 1, 4, 3, 1, 2, 5, 3, 5];}

Well done for that. Its been windy here and "wind = power outage"
where I live :-)

One day I'll get a decent size UPS.

Best Regards,

Kevin.
• ... The current record is length 112, achieved by {sphen112a = [114, 3, 6, 6, 3, 2, 2, 1, 3, 3, 2, 2, 1, 5, 2, 3, 2, 1, 6, 4, 4, 2, 4, 4, 2, 5, 4, 2, 3, 4, 2,
Message 16 of 16 , Jun 23, 2011
• 0 Attachment
Kevin Acres <research@...> wrote:

> > {sphen109 = [114,
....
> Well done for that. Its been windy here and "wind = power outage"
> where I live :-)

The current record is length 112, achieved by

{sphen112a = [114,
3, 6, 6, 3, 2, 2, 1, 3, 3, 2, 2, 1, 5, 2, 3, 2, 1, 6, 4, 4,
2, 4, 4, 2, 5, 4, 2, 3, 4, 2, 1, 3, 3, 6, 5, 4, 3, 1, 5, 4,
2, 5, 1, 1, 3, 4, 5, 5, 5, 5, 6, 3, 6, 1, 6, 1, 4, 3, 1, 6,
4, 6, 3, 1, 3, 2, 1, 2, 2, 6, 3, 2, 3, 5, 4, 6, 6, 5, 2, 2,
2, 3, 4, 6, 5, 2, 3, 3, 2, 6, 5, 1, 2, 6, 1, 4, 3, 5, 3, 3,
3, 4, 1, 4, 2, 2, 1, 2, 6, 3, 2];}

{sphen112b = [114,
3, 6, 6, 3, 2, 2, 1, 3, 3, 2, 2, 1, 5, 2, 3, 2, 1, 6, 4, 4,
2, 4, 4, 2, 5, 4, 2, 3, 4, 2, 1, 3, 3, 6, 5, 4, 3, 1, 5, 4,
2, 5, 1, 1, 3, 4, 5, 5, 5, 5, 6, 3, 6, 1, 6, 1, 4, 3, 1, 6,
4, 6, 3, 1, 3, 2, 1, 2, 2, 6, 3, 2, 3, 5, 4, 6, 6, 5, 2, 2,
2, 3, 4, 6, 5, 2, 3, 3, 2, 6, 5, 1, 2, 6, 1, 4, 3, 2, 3, 3,
4, 2, 2, 3, 2, 2, 1, 4, 5, 1, 1];}

with input and output in