Sequence terminations and merges

[Batalov]

7 more

1176774 690642
1179288 372402
1267152 315636
1311728 1093928
1344648 1112448
1454880 722064
1618830 1201808

[R. Gerbicz]

Originally Posted by Dubslow

How on earth did you do that? I count 405 mergers in your data, which includes 36 that had already been detected. What are your methods? How long did it take? Had you been doing local calculations in the early/low portions of the various seqs, or have you solely been massaging the rechenkraft data? (AllSeq.txt doesn't even have IDs! Though I suppose string comparison on the factors lines would have been just as good.) If the latter, what massaging? How much have you queried the FDB?

Zero factordb queries, just a simple single threaded Pari-Gp code using the starting values from AllSeq.txt, it took roughly 25 minutes, working from scratch. When raised the limit to 10^40 surprisingly it has found only one more collision in 2 hours:

1382088 28008

but it has been already deleted from the newer AllSeq.txt file.

[Batalov]

Here is my code (one can rerun it with M=1e13 if you want to find more trivial merges).

# gp

% too lazy to detect cycles, so "for(i=0,100,"

M=10^12;forstep(x=2,2000000,2,a=x;for(i=0,100,s=sigma(a)-a;write("ALL_10_12",x" "s);if(s==a||s>M||s<=x,break);a=s))
% or
M=10^12;for(x=2,2000000,a=x;for(i=0,100,s=sigma(a)-a;write("ALL_1e12",x" "s);if(s==a||s>M||s<=x,break);a=s))

awk '{if($1<$2){print} else {print $2, $1}}' ALL_1e12 |sort -n |uniq > ALL_1e12a

_merger.pl
#!/usr/bin/perl -w

open IN, "<ALL_1e12a";
while(<IN>) {
  /(\d+) (\d+)/;
  if($B{$2} && $B{$2} < $1) {
    $B{$1} = $B{$2};
  } else {
    $B{$2} = $1;
  }
}
close IN;

for($i=4;$i<=2000000;$i+=2) {
  print $i, " ",$B{$i}, "\n" if ($B{$i} && $B{$i} <= $i);
}

All trivial merges up to 2M at 12-digit level are attached.

[R. Gerbicz]

My used Pari-Gp code was:

allocatemem(10^8);
ffun(filename,B)={v=vecsort(readvec(filename));L=length(v);T=vector(L);nc=0;for(i=1,L,n=v[i];
print("Test n=",n,"; collisions=",nc);while(n<B,n=sigma(n)-n;if(n>=B,T[i]=n;
for(j=1,i-1,if(n==T[j],write("merges.txt",v[i]" "v[j]);print(v[i]" "v[j]);
nc+=1;break()));break())));return(nc)}

Call it for example: ffun("in.txt",10^50) where the first parameter is the master file, one starting number per line, sorted in increasing order; since we read the file by readvec this input format is strict. The second number is the search limit.
(You can try it using a smaller input file, containing some trivial collision(s).)
Attached the sample in.txt file for n<2M. I've already done it with ffun("in.txt",10^40).
The collisions saved to merges.txt file, also printed to screen.

[Dubslow]

Why is GP nearly as illegible as Perl

[Batalov]

Originally Posted by Dubslow

How on earth did you do that?

Originally Posted by Dubslow

Why is GP nearly as illegible as Perl?

These questions are ultimately connected.

[Dubslow]

Originally Posted by Batalov

These questions are ultimately connected.

PARI has a Python frontend in the Sage package, unfortunately Sage still isn't py3k compatible Soon™!

[richs]

1382232 terminates at i3532. It merges with 1262272 at i3429.

[axn]

Originally Posted by Dubslow

Why is GP nearly as illegible as Perl

Originally Posted by Dubslow

PARI has a Python frontend in the Sage package, unfortunately Sage still isn't py3k compatible Soon™!

How about now? Is this really inferior to Python?

allocatemem(10^8);
ffun(filename,B)=
{
	v=vecsort(readvec(filename));
	L=length(v);
	T=vector(L);
	nc=0;
	for(i=1,L,
		n=v[i];
		print("Test n=",n,"; collisions=",nc);
		while(n<B,
			n=sigma(n)-n;
			if(n>=B,
				T[i]=n;
				for(j=1,i-1,
					if(n==T[j],
						write("merges.txt",v[i]" "v[j]);
						print(v[i]" "v[j]);
						nc+=1;
						break()
					)
				);
				break()
			)
		)
	);

	return(nc)
}

[Dubslow]

Originally Posted by axn

How about now? Is this really inferior to Python?

allocatemem(10^8);
ffun(filename,B)=
{
	v=vecsort(readvec(filename));
	L=length(v);
	T=vector(L);
	nc=0;
	for(i=1,L,
		n=v[i];
		print("Test n=",n,"; collisions=",nc);
		while(n<B,
			n=sigma(n)-n;
			if(n>=B,
				T[i]=n;
				for(j=1,i-1,
					if(n==T[j],
						write("merges.txt",v[i]" "v[j]);
						print(v[i]" "v[j]);
						nc+=1;
						break()
					)
				);
				break()
			)
		)
	);

	return(nc)
}

That's much better, thanks! I'm figuring out thanks to your indentation that commas and semicolons inside loops have the opposite meaning from what they have in C.

Here's a rough equivalent in Python, if anyone wants to compare. Of course the major disadvantage of Python is that it doesn't offer any functions for number theory, so it uses the crappy sigma I rolled long ago for the blue page. (Sage uses Pari among many other fast backends, so Python+Sage would not have the same problem, though as before, Sage doesn't quite yet support modern Python versions.)

#! /usr/bin/env python3

from collections import defaultdict

from mfaliquot.theory.numtheory import sigma
# ^ shitty hand rolled python, much slower than pari
# if/when sage supports python3, it would be as fast as pari

def ffun(filename, B):

     with open(filename) as f:
          v = list(sorted(int(line) for line in f))

     T = defaultdict(list)
     nc = 0

     for seq in v:
          print("Test seq=", seq, "; collisions=", nc)
          n = seq
          while n < B:
               n = sigma(n) - n
               if n >= B:
                    l = T[seq]
                    if l:
                         nc += 1
                         with open("merges.txt", 'w') as f:
                              f.write("{} {}".format(seq, n))
                    l.append(n)
                    break

     return nc

if __name__ == '__main__':
     from sys import argv
     ffun(argv[1], eval(argv[2]))

The defaultdict(list) is exactly what the blue page uses as well to find mergers. I had thought the equivalent search for trivial merges like this had already been done, otherwise I would have done it myself. At least we'll be prepared when further extensions come.

bill@Gravemind ~/mfaliquot $ time ./gp_ali.py in.txt "10**15"
...
...
real	88m24.983s
user	87m37.980s
sys	0m46.180s

Can confirm no collisions and also slow as ****

[R. Gerbicz]

Originally Posted by Dubslow

PARI has a Python frontend in the Sage package, unfortunately Sage still isn't py3k compatible Soon™!

Pari is available in Linux and Windows also.

Small note to the above ffun() routine: it is assuming that all sequences in the file reach the B bound, if it is not true, then there'll be an infinite loop. (It wouldn't be that hard to modify it to handle this also.)