Factor bothering

In Part 3 I found that I could optimize the factor generation code I made in Part 1. Here's the new code:

genFastFactors.pl my $x,$y; my $max=$ARGV[0]; my $sqrtMax=sqrt($max); my @arrFactors; for($x=2;$x<=$sqrtMax;$x++) { my $maxY=$max/$x; for($y=$x;$y<=$maxY;$y++) { @arrFactors[$x*$y].="$x $y "; } } my $arrLen=@arrFactors; for(my $line=1;$line<$arrLen;$line++) { print "$arrFactors[$line]\n"; }

I set this running to calculate the factors for the first ten million integers and went and had a cuppa, came back and it was done!

Trouble is if I try to make it do more than ten million I'm in a world of pain. It's a memory hog, anything more than ten million completely chewed my virtual memory and thrashed my hard drive.

This should be easy to resolve as I was storing the factors as strings, if I store them as the integers they are, fingers crossed, it'll be much better. Assuming Perl plays nice.

I've made the changes to store integers, not strings, but it had no noticable effect on memory although I think it has improved the speed even more!

So I'm going for a different tack with regards to memory; don't store the first 10 million, they've already been generated!

The following script takes two arguments, the minimum and the maximum integers needing factorizing.

genFastFactors2.pl my $intY,$intX; my $intMin=$ARGV[0]; my $intMax=$ARGV[1]; my $sqrtMax=sqrt($intMax); my @arrFactors; my $maxX=0; my $multipliedValue=0; for($intY=2;$intY<=$sqrtMax;$intY++) { $maxX=$intMax/$intY; for($intX=$intY;$intX<=$maxX;$intX++) { $multipliedValue=($intY*$intX)-$intMin; if($multipliedValue>0) { push(@{$arrFactors[$multipliedValue]},$intY); push(@{$arrFactors[$multipliedValue]},$intX); } } } foreach my $FactorList(@arrFactors) { print join(" ",@{$FactorList})."\n"; }

The above generates the factors between ten million and eleven million and appends the result onto factorTenMill.txt which of course is now mis-named.

I've now been able to create a file with the factors for the first fifteen million integers (weighing in at 1.026 gigabytes).

Can you spot the difference? Hover your mouse over the graph to see the histogram from part 2.

I'm prepared to say that there is something reasonably special about having 60 factors, it's either very rare or impossible. I'd be surprised if it is impossible, I'm quite daunted about being able to show that though.

I guess the first thing to do is have a look at numbers with 58 and 62 factors, will need to go through our factors and spit them out:

extract58and62.py import os,sys factorFile=open('factors15Mill.txt','r') intInteger=1; for line in factorFile: factorCount=len(line.split()) if factorCount>=58 and factorCount <=62: print intInteger,factorCount,":",line intInteger+=1; factorFile.close()

146290 integers with 58 or 62 factors ranging from 5040 (with 58 factors) to 14999965 (with 62 factors) in the first 15 million integers, 0 integers with 60 factors.

plot58and62factors.py import Image, ImageDraw import os,sys import math size = 5000,5000 im=Image.new("1",size) draw=ImageDraw.Draw(im) draw.rectangle(((0,0),size),1) #set image bg to white factorFile=open("58and62factors.txt",'r') for line in factorFile: factors=line.split() factorlen=len(factors) for pointxy in range(3,factorlen,2): #print pointxy,factors[pointxy],factors[pointxy+1] x=int(factors[pointxy]) y=int(factors[pointxy+1]) draw.point((x,y),0) factorFile.close() im.save("58and62factors.png","PNG")

I was expecting some "trails" that would lead done to the botton right, certainly not any horizontal and vertical patterns!

Maybe it's because I am plotting the integers with both 58 and 62 factors? They might be obscuring each other...

There certainly was some interference between 58 and 62 factors. 58 factors seems to have a wider spacing between the "grid lines" while 62 factors has finer "grid lines" but less distinct.

I'm just generating more and more questions here! What are these grids? Why are they there?

Factor bothering - Part 4