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. :hyper:

[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?

:hyper:

 

___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? :hyper:

[Turtle]

The first data set; integers from 1 to 113,000. :hyper: {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 pairsn",maxcounter,numberofdivisors);

printf("%10st%10st%10st%10sn","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("%10dt%10dt%10dt%10dn",counter,sum, difference, elements);

}

return 0;

}

[Buffy]

Here's some sample output:

F:srcintstatdebug 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

[Turtle]

"Lucy! You got sum 'splainin to do." ;) This is great Buffy! First, you are quite right to ask what is SUM & DIFF doing here because they don't figure in trapping ELEMENTS. I use this basic (a double entendre) program contruct for my main experimental platform. You will find SUM & DIFF used in the experiments described in threads "Strange Numbers" & "Big R".

Your output is incorrect, so even though I don't know C++, I know your code needs tweeking. Now if I can just get you to arrange your output this way, including printing the label to screen. Each succesive loop results should overwrite in the same position. See?

your output correct output

1 COUNTER 1 COUNTER

2 SUM 1 SUM

1 DIFF 0 DIFF

1 ELEMENTS 2 ELEMENTS

 

Remember we are using the standard definition of perfect numbers, ie. you sum all the proper divisors, including 1 but NOT the number itself. Technically 1 has two ELEMENTS, 1 & 1. The second 1 is the one that is "itself" so you must not count it. The SUM is therefore 1, not 2. The DIFF is therefore 0 (get ready for this claim!) & since this is the very definition of Perfect Numbers, I argue 1 is Perfect. 6 is universally considered the first Perfect. Even further under this experiment 1 is not only perfect but prime as well. Strickly speaking, 1 is Prime but to consider it so makes for some very nasty calculations.

The things I have found, I found because I had these 4 variables flashing by on my screen as I just set there & watched. For weeks. When I saw something interesting I'd interupt the run & code a trap & then start it again & watch; for weeks. If I can get others watching in the same way, there is much to be discovered.

Finally, in the case of 4 & 16: Mmmmm...we'll wait on this one because it doesn't affect the ELEMENTS. Think about them though.

The data set images may make more sense when you digest all this. ;)

[Buffy]

Okay, so to try to define what these terms mean:

 

Elements: This should be the number of divisors, including 1 but not including Counter for each Counter. My current code counts *pairs* of divisors, and this is wrong, right?

 

Sum: Like the Elements, this is the sum of all divisors, including 1 but not Counter. My current code includes Counter so its off.

 

Difference: The Sum minus the Counter (which has already been left out of the Sum). My current code is spitting out the Sum in this column (I think!).

 

On a fast machine, its basically impossible to watch this stuff whether it scrolls or just overwrites the line. On my "slow" machine (1.8ghz) it does Counter going up to 1 million in about 5 seconds. It probably begs a different display that only shows the statistics for each number of divisors (Elements going up in the left column, rather than Counter), which is what I thought your scans show (but I can't read your handwriting...). I'd have to add a data structure to capture em though!

 

Cheers,

Buffy

[Turtle]

Question: Elements: This should be the number of divisors, including 1 but not including Counter for each Counter. My current code counts *pairs* of divisors, and this is wrong, right?

 

Answer: ELEMENTS should be the number of divisors. Period. Simply the tally. If you coded to count pairs, multiply number of pairs by 2= ELEMENTS.

 

Question: Sum: Like the Elements, this is the sum of all divisors, including 1 but not Counter. My current code includes Counter so its off.

 

Answer: This is correct. Remembering still SUM doesn't figure in this specific experiment.

 

Question: Difference: The Sum minus the Counter (which has already been left out of the Sum). My current code is spitting out the Sum in this column (I think!).

 

Answer: This is correct. Remembering still DIFF doesn't figure in this specific experiment.

 

Question: On a fast machine, its basically impossible to watch this stuff whether it scrolls or just overwrites the line

 

Answer: When you start, you may want to code a delay in order to watch. Here is where your willingness to participate with your fast machine is simply wonderful! If you are familiar with the "Big O" function , it applies to how fast a program's output slow down as the size of the input increases. The faster you go, the behinder you get. I have only a 200mghz machine & can only search so fast. (and I only can search so far since my Turbo Basic I use has an integer limit of just over 2 billion.)

 

Question: I'd have to add a data structure to capture em though

 

Answer: That's the ticket.

 

PS I'll see what I can do with better scans, but my handwriting...

;)

[Turtle]

I thought to write as simple an explanation as possible here while Buffy works up some code.

Imagine before you the list of integers in order & stretching off into infinity. Imagine also a collection of tally wheels(like odometers), marked in order by twos (tally wheel labeled 2, wheel labled 4, etc.) & also stretching off to infinity. Set all your tallys to zero. Now begin factoring the integers one at a time from 1 & count how many divisors each integer has. Find the tally wheel for that number of divisors & advance it by 1. Now go to the next integer & do the same.

The pattern I want you to see is how the tallies are distributed among the "tally wheels" & how this distribution changes as you factor more & larger integers.

I hope that helps clarrify the experiment. :)

[Turtle]

Attached below, data sets 4 & 5. I apologize for my handwriting & poor quality of scans. I never programmed code to save these results to files or arrays; instead, I simply paused the run & wrote the data down from my display. By introducing these discoveries, I hope to prompt those of you with greater computer resources to do that which I cannot.

This experiment, and those related experiments I describe in other threads, stands strictly on the 2,500 year old Greek concept of Perfect Numbers. It is often the case a new supercomputer coming on line is put through it's paces looking for the next largest perfect number. What I am doing, and suggest others do as well, is to look at the discards during the search for Perfect Numbers to see what else we may discover. :)

[Turtle]

In order to clear the waters here that I've muddied up a bit, I am starting to take new data sets from the experiment running in the thread "Big "R" & the hunt for Phat Numbers". Further, I will type up my handwritten list drawn from the display directly here. Here again I realize how uniquelly suited Hypography is to my work which frequently uses long lists. Just scroll down! From scrolls to books and back. :cup:

Edit Section:

 

Of the first 15,190,999 integers sieved:

 

Class by #

of divisors Tally

 

2 982,246

4 2,844,640

6 525,511

8 3,376,836

10 96,791

12 1,250,499

14 23,557

16 2,189,013

18 104,248

20 207,102

22 1,933

24 1,125,658

26 542

28 47,629

30 30,477

32 842,993

34 83

36 183,166

38 15

40 159,587

42 7,242

44 2,917

46 371

48 497,690

50 1,849

52 743

54 10,543

56 31,687

58 3

60 45,452

62 0

64 190,863

66 558

68 43

70 770

72 105,796

74 0

76 70

78 161

80 55,185

82 174

84 9,046

86 1

88 1,447

90 3,572

92 1

94 0

96 110,229

98 69

100 2,239

102 10

104 289

106 38

108 10,114

110 53

112 8,881

114 1

116 0

118 0

120 19,406

122 0

124 0

126 753

128 22,363

130 13

132 424

134 0

136 94

138 0

140 683

142 or more divisors 56,621

[Turtle]

___That still looks like &!!#%. I will see if I can learn some spread sheet for this maybe. Nonetheless, if you look at the last list, how weird is it that in the first 15 million+ integers, only 1 has 92 divisors, none have 94 divisors, & then all of a sudden 110,229 have 96 divisors! :(