Statisitical View Of Integers Grouped By Number Of Divisors

[Turtle]

This is an exposition on a computer experiment in factoring the sequential integers. A statistical approach is used to group the set of integers according to how many divisors an integer has. This is all very familiar territory in the case of integers with 2 divisors (1 pair); these of course are the primes. The distribution of the group of primes among the integers is well studied, including measuring the changing ratio of primes/integers as one ascends the infinite set of integers.
Perhaps less well known is the next group in the list of groups, namely the group of integers which have just 2 pairsof divisors. The first pair of course is 1 & the number itself, & the second pair is 2 primes. This group is the set called psuedo-primes, & they have considerable use in cryptography.
This is where we depart & start asking the same measure questions established above about the other groups in this class. What is the distribution of integers with 3 pairs of divisors, 4 pairs, 5 pairs, etc.
Take some little time to consider this proposition, & in my next post I'll present some pseudo code for you.

[Turtle]

Here we go then:

start a loop at 1 which increments by 1 'call the variable COUNTER
take the square root of COUNTER & drop any fractional part 'call the variable MAXELEMENTS
start a loop at 1 going to MAXELEMENTS 'call the variable INDEX
Divide Counter by INDEX 'call the varible TEMP
Drop any fractional part of TEMP & compare it to TEMP ;call variable TEMP2
If TEMP2=TEMP then you have a divisor; otherwise not
If you have a divisor, you have it's pair. Save them in an array variable
loop
count the number of pairs & save in a varible 'call it ELEMENTS
sum the pairs & put in variable SUM
subtact COUNTER from SUM & put in variable DIFFERENCE
display in top left corner of the screen, top to bottom, the variables COUNTER, SUM, DIFFERENNCE. & ELEMENTS

loop

Any questions?


___Very well. For this experiment the data set we will collect is drawn from the variable ELEMENTS. Additional to the code above, establish variables to hold the counts of the group types, ie. a variable to hold the incremental count of the occurance of a number with 1 pair of divisors, a variable for 2 pairs, 3 pairs, etc. In the version running currently I have the first 121 groups displaying, & one group variable collecting & displaying the number of occurances of more than 121 divisors. The coming data sets I will be posting come from a run several years ago, but they well illustrate the concept.
I have never run an experiment on any thing faster than a 200mghz, so I hope to entice some of you readers who have big bad fast machines to bravely go where no one has gone before. Next time I should have some data to post & things may clarify for everyone.

[Tormod]

Turtle, you should write some articles for us about these things. It's very interesting stuff.

[Turtle]

Thanks Tormod; I found them interesting too & thought it was time to share it. I can't say too many times what a unique opportunity you have offered me (& everyone) here for sharing this kind of info. Thank you! If you want to put this stuff somewhere besides the regular postings just let me know. You didn't know that turtle's could juggle did ya?

[Turtle]

The first data set; integers from 1 to 113,000. {See attachment post #7}

[Turtle]

Now before posting the next data set, let me point out the salient features of the first. In the left two columns, the ordered lists of possible numbers of divisors, expressed in the leftmost as the full count & in the rightmost as pairs. At the top, 113,000 integers factored in order, & a tabulation taken. Below this in the main column, read it as follows: Of the first 113,000 integers, 10,770(exactly) have 1 pair of divisors. The primes of course. Further, of the first 113,000 integers, 67 have 2 pairs (psuedo-primes). Continue in this manner down the list.
After the count entries, an arrow points right to a decimal fraction that is the ratio of the count entry to the total integers factored. So in the case of primes, 10,700/113,000 = .094690265.
A very interesting distribution is shaping up here; do you see? Next post, the second data set.

[Turtle]

The second data set, together with the first. A note on my method here: to gather the data sets I simply interupted the run long enough to get the most current stats. Because I did this collecting around my human schedule, the data sets are not evenly spaced; nonetheless, the developing distribution is clear.

[Turtle]

Come Mr. Talleyman, tally my bananas... I couldn't remeber the word "tally" for days. So, here's the 3rd tally. I'll post the rest in pairs, & then to infinity & beyond... I have this experiment running as we speak; it is at just over 12,000,000 & has run a week or two. Of course it's steadily slowing, but that's exactly what makes this work hard.
I don't know if you had any expectation of what the distribution would look like from my description of the experiment;i guess I though it would be some smooth kinda curve, not chaotically wiggly.
One last note: in this new third column, at it's extreme right edge, appear some arrows. If the arrow points up, the percentage has gone up since the last data sample; if the aroow points down, the percentage has dropped. Mmmmm.... which way do they point in the next data set? Do any settle down to one direction or other? What will they do next?!

[Buffy]

This is fun! Below is a simple C++ program that implements Turtle's pseudocode (bit different method for detecting divisors, taking advantage of the C++ modulo operator).

Turtle: I couldn't follow your images, and I'm still mystified by what you're doing with the sum and difference columns, and I don't know that I interpreted your pseudocode correctly. Can you 'splain these a bit more?

Cheers,
Buffy

#define MAXCOUNTER 100
// if NUMBEROFDIVISORS = 0, print ALL numbers from 1 to MAXCOUNTER
// if NUMBEROFDIVISORS > 0, print ONLY numbers with that number of pairs of divisors
#define NUMBEROFDIVISORS 0
int main(int argc, char *argv[])
{
int maxcounter = MAXCOUNTER;
int numberofdivisors = NUMBEROFDIVISORS;
int counter;
int maxelements;
int index;
int remainder, divisor1, divisor2;
int elements, sum, difference;
if (argc > 1) maxcounter = atoi(argv[1]);
if (argc > 2) numberofdivisors = atoi(argv[2]);
printf("Running integer statistics from 1 to %d, with %d divisor pairs\n",maxcounter,numberofdivisors);
printf("%10s\t%10s\t%10s\t%10s\n","counter","sum", "difference","elements");
for (counter=1;counter<=maxcounter;counter++) {
maxelements=(int) floor(sqrt((double) counter));
elements=0; sum=0;
for (index=1; index<=maxelements; index++) {
remainder = counter % index;
if (remainder == 0) {
divisor1 = counter / index;
divisor2 = index;
sum += (divisor1 + divisor2);
elements++;
}
}
difference = sum - counter;
if (numberofdivisors == 0 || elements == numberofdivisors)
printf("%10d\t%10d\t%10d\t%10d\n",counter,sum, difference, elements);
}
return 0;
}

[Buffy]

Here's some sample output:
F:\src\intstat\debug Godzilla2! intstat 30 0
Running integer statistics from 1 to 30, with 0 divisor pairs
counter sum difference elements
1 2 1 1
2 3 1 1
3 4 1 1
4 9 5 2
5 6 1 1
6 12 6 2
7 8 1 1
8 15 7 2
9 16 7 2
10 18 8 2
11 12 1 1
12 28 16 3
13 14 1 1
14 24 10 2
15 24 9 2
16 35 19 3
17 18 1 1
18 39 21 3
19 20 1 1
20 42 22 3
21 32 11 2
22 36 14 2
23 24 1 1
24 60 36 4
25 36 11 2
26 42 16 2
27 40 13 2
28 56 28 3
29 30 1 1
30 72 42 4