A Truly Worthwhile Challenge.

[Don Blazys]

Just to let you know i am getting a pretty beefy CPU for Christmas,

so such a project may be unnecessary.

 

That's great phillip. You more than deserve it!

 

Besides, the school already did a lot of favors for me,

(including putting up my website) and I hate to impose.

 

Let's make the school "plan B" and test that CPU

on this truly serious and important calculation!

 

:D

 

Don.

[phillip1882]

got my pc today, how big would you like me to go? remember larger numbers = more time to calculate.

[Don Blazys]

First off... let me say...Merry Christmas Phillip 1882!

 

As you can see here:

 

http://donblazys.com/on_polygonal_numbers_3.pdf

 

the present record is just above [math]\varpi(10^{12})[/math],

 

and while this allows us to verify that the present value of the Fine Structure Constant

is well within the upper and lower bounds as predicted by the counting function,

it does not allow us to determine any extra digits of the Fine Structure Constant.

 

In order to determine the Fine Structure Constant to say,

14 solid and significant digits,

we would probably need [math]\varpi(10^{17})[/math] or so.

 

Then again, [math]\varpi(10^{20})[/math] would probably get us a good solid

value of the Fine Structure Constant to 17 or 18 digits...

but that might be asking too much.

 

Since I don't know anything about the power and speed of your new machine,

let's just "play it by ear" and "make it up as we go along"!

 

Just keep in mind that what we are doing here is really quite new...

and honestly, you couldn't have picked a more worthwhile series of

calculations with which to test the power of your new machine.

 

After all, the folks at the Online Encyclopedia of Integer Sequences are

very interested in this and your work will definitely be credited there.

 

Moreover, if the random and erratic fluctuations of [math]\varpi(x)[/math]

just happen to result in upper and lower values of the Fine Structure Constant

that correspond to, correlate with and match the findings described in this article:

 

http://www.science20.com/news_articles/if_finestructure_constant_varies_then_laws_physics_throughout_universe_do_too

 

then we will really have something to think (and maybe sing) about!

 

Don.

[phillip1882]

hmmm...

it took 6 hours to get to 10^10 with my algorithm.

assuming time increases at the same rate the number does 10^17 would be...

6*10^7 = 60,000,000 hours. that's 6849 years. i doubt you wanna wait that long. i have an idea however about how to speed it up. let me try a few things and see how it works out.

[Don Blazys]

Well, any value of [math]\varpi(x)[/math] that breaks the present record would be

a most welcome improvement. Win or lose, it's important that we at least try.

 

Don.

[phillip1882]

so here was my idea, use the lower powers to get an answer for the higher powers.

the main problem with my algorithm is that the lower values take a long time to calculate.

so i thought if i did some precalculation that would speed things up. well i definitely get the speed up, however, now my answer is off by about 500 (for 10**9).

not quite sure where to go from here. would you mind a less than 1% margin of error?

[Don Blazys]

How much is it off by at [math]10^2, 10^3, 10^4, 10^5...[/math]

 

Maybe we could determine and establish a pattern and compensate accordingly.

 

Otherwise,(if there is no such pattern), the data would be useless because

 

at [math]\varpi(10^{9})[/math] the counting function itself is off by only [math]111[/math].

 

Don.

[phillip1882]

10^3 is too small for precalculation. (that is i get the exact value, no precalc done.)

10^4 i get 6359 (actual is 6357)

10^5 i get 63902 (actual is 63889)

10^6 i get 639839 (actual is 639926)

10^7 i get 6402081 (actual is 6402325)

10^8 i get 64031814 (actual is 64032121)

10^9 i get 640347944 (actual is 640349979)

here's basically the guts of my idea:

tempmax = max/10

count = total for tempmax

new total = count +int((max-tempmax)/column *count/((tempmax-row)/column)) +1

in plain English, i use 10% less the maximum to determine the percentage of values in the maximum that appear. while each approximation is off by less than %1, it can quickly add up as you can see.

the speed advantage is significant, nearly 4 times faster.

[Don Blazys]

Sorry Phillip 1882,

 

I don't see a pattern that can help us, but in truth, not having the values of [math]\varpi(x)[/math] that would

allow us to further refine the value of the fine structure constant is only a minor setback.

 

In principle, this counting function still defines the fine structure constant

in a way that no mere observation of some physical phenomena ever can!

 

You are a true warrior. Thanks for the valiant effort and for being a part of it.

 

Don.

[Turtle]

To: Phillip 1882,

 

...The present "world record" , which is [math]\varpi(1,100,000,000,000)[/math] was achieved using code written by that great Hypographer...

 

"Donk", who I respect and admire.

 

His code seems pretty simple and straightforward, and would probably suffice if programmed into a sufficiently fast and powerful machine.

 

One thing for sure, his code works (where everyone else's caused their computers to fail or "crash"),

 

so I'm quite certain that if he were to gain access to a "supercomputer", then [math]\varpi(10^{20})[/math] would be a "piece of cake" !

 

This forum has some pretty "heavy hitters", and perhaps if a "team" were to form, then that simple, yet important question:

 

"How many regular figurative numbers are there under a given number [math]x[/math]?"

 

would finally get answered up to some satisfying and respectable values of [math]x[/math]... just like [math]\pi(x)[/math] was!

 

Don.

 

i'm not sure if donk posted his code, but i'm looking. in the mean time if it's a matter of benchmarking phillip's new machine with some curse definitve & tested code, modest gave us that in post #6 of the non-figurate numbers thread.

 

I don't think so. I'm pretty ridiculously bad at that sort of thing though.

 

I think this code would work for a brute force kind of search:

 

for($checknum = 6; $checknum < 1000; $checknum++){
 $found = 0;
 for($n = 2; $n < $checknum and $found == 0; $n++) {
   for($s = 2; $s < $checknum and $found == 0; $s++) {
   if (($n/2)*(($s-2)*$n-$s+4) == $checknum) {$found = 1;}
   }
 }
 if ($found == 0) {print "$checknum, ";}
}

 

F < 1000 =

 

7,8,11,13,14,17,19,20,23,26,29,31,32,37,38,41,43,44,47,50,53
,56,59,61,62,67,68,71,73,74,77,79,80,83,86,89,97,98,101,103,
104,107,109,110,113,116,119,122,127,128,131,134,137,139,140,143,
146,149,151,152,157,158,161,163,164,167,170,173,179,181,182,187,
188,191,193,194,197,199,200,203,206,209,211,212,218,221,223,224,
227,229,230,233,236,239,241,242,248,251,254,257,263,266,269,271,
272,277,278,281,283,284,290,293,296,299,302,307,308,311,313,314,
317,319,320,323,326,329,331,332,337,338,347,349,350,353,356,359,
362,367,368,371,373,374,377,379,380,383,386,389,391,392,397,398,
401,404,407,409,410,413,416,419,421,422,431,433,434,437,439,440,
443,446,449,452,457,458,461,463,464,467,470,473,476,479,482,487,
488,491,493,494,497,499,500,503,509,517,518,521,523,524,527,530,
533,536,539,541,542,547,548,551,554,557,563,566,569,571,572,577,
578,581,583,584,587,589,593,599,601,602,607,608,611,613,614,617,
619,620,623,626,629,631,632,638,641,643,644,647,649,650,653,656,
659,661,662,667,668,673,674,677,683,686,689,691,692,698,701,704,
707,709,710,713,716,719,722,727,728,731,733,734,737,739,740,743,
746,749,751,752,757,758,761,767,769,770,773,776,779,787,788,791,
794,797,799,800,803,806,809,811,812,817,818,821,823,824,827,829,
830,839,842,851,853,854,857,859,860,863,866,869,872,877,878,881,
883,884,887,890,893,896,899,901,902,907,908,911,913,914,917,919,
920,923,926,929,937,938,941,943,944,947,950,953,956,959,962,967,
968,971,974,977,979,980,983,986,989,991,992,997,998,

 

Do those look correct?

 

I'll try to figure out a sequence or function.

 

~modest

 

note that modest's program does use donk's algorithmic test for non-figurates, and that it outputs & counts non-figurates. to find the number of figurates (i.e. polygonals) < F, subtract the output count of non-figurates <F from F.

[Don Blazys]

Coincidentally, as you were posting the above, I was viewing some of your artwork.

(The "avatars", some of which are really eye-catching and fun to analize.)

 

Merry Christmas!

 

Don.

[phillip1882]

hey turtle, it's not just a matter of accurately getting the number, its doing so in a reasonable amount of time.

i have an algorithm that can get 10^6 in less than a minute, the one you provided takes several. however, even my algorithm begins to stumble at large powers. 10^9 takes about 20 minutes. 10^10 takes about 6 hours. i could break the record and go for 10^13 perhaps, that would take roughly 3/4 of a year; but not much larger.

i tried a new idea to get a speed up, but it no longer gets the accuracy.

[Turtle]

hey turtle, it's not just a matter of accurately getting the number, its doing so in a reasonable amount of time.

i have an algorithm that can get 10^6 in less than a minute, the one you provided takes several. however, even my algorithm begins to stumble at large powers. 10^9 takes about 20 minutes. 10^10 takes about 6 hours. i could break the record and go for 10^13 perhaps, that would take roughly 3/4 of a year; but not much larger.

i tried a new idea to get a speed up, but it no longer gets the accuracy.

 

well, for don's purposes it is a matter of accuracy. since we have exact data from donk out to 100 billion (is that right?), then you can set the starting point in modest's program at one more than that and search forward. while shortcuts would be nice, i don't think we have any such workable approaches. one caveat though; using modest's program that looks for non-figs, we can skip every 3^rd number because we have proven that every multiple of 3 is figurate.

 

with the problem broken into modest sized blocks (;)), we could look for folks willing to run them in a distributed computing scheme.

 

Coincidentally, as you were posting the above, I was viewing some of your artwork.

(The "avatars", some of which are really eye-catching and fun to analize.)

 

Merry Christmas!

 

Don.

 

:xmas_sheep: thnx don.

 

In art the hand can never execute anything higher than the heart can inspire. ~ Ralph Waldo Emerson

[Turtle]

found some links to donks:

 

donk's q-basic code: post #86

http://scienceforums.com/topic/19130-non-figurate-numbers/page__view__findpost__p__285598

 

donk's list to 1 billion: post #127

http://scienceforums.com/topic/19130-non-figurate-numbers/page__view__findpost__p__286206

 

donk explains sieve: post #136

http://scienceforums.com/topic/19130-non-figurate-numbers/page__view__findpost__p__286613

 

The problem is that it's a sieve. You have to have all the numbers available, because you're striking them out one by one, starting from the beginning again for each new value of n.

 

Since I could only manage a piddling 32K of data in memory, I was forced to use disc access. I set up a random-access file, 4096 bytes per record, one gigabyte in size. I then filled the whole file with zeros. To strike out number X, I used (the integer part of X/4096)+1 for the record number, and X mod 4096 for the point within the record. Read the record, change the value from a zero to a space, write it back down, move on to the next X. (It would have been impossibly slow when I was doing this sort of thing ten years ago, but discs are faster and disc caches are better.)

 

Only when the whole routine has been run can we determine what the final list is. We open up the file, record by record, ignoring the spaces and printing the position of all the zeros. Into another file, naturally - over 4gigabytes, so I split it into 1000 4-meg-ish files. After that I had to do the further processing to determine whether each number was prime or composite - another 9 gigabytes' worth here. Good fun :confused:

 

seems to me donk's program is not well suited to distributed computing, wheras modest's is. i think craig gave an algorithm -if not code- using yet a third approach for the search. i will keep an eye out for it as i re-read the thread.

[modest]

seems to me donk's program is not well suited to distributed computing, wheras modest's is. i think craig gave an algorithm -if not code- using yet a third approach for the search. i will keep an eye out for it as i re-read the thread.

 

Really, my code from post #6 should be stricken from the record.... never to be mentioned in polite company :)

 

It was mostly a quick method of getting the first 100 or so non-figs. Craig's is superior in every respect. I've coded it in perl:

 

use Math::BigFloat;

for ($x = Math::BigFloat->new(1000000000,20); $x < 2000000000; $x++){
 my $s = Math::BigFloat->new(3,20);
 my $n = Math::BigFloat->new(3,20);

 while ($s > 2){
   $s = (2*$x + 2*$n**2 - 4*$n)/($n**2 - $n);
   if ($s < 3){print int($x)," is nonfig \n"; last;}
   if ($s == int($s)){print int($x)," is figurate at n = ",int($n),", s = ",int($s),"\n"; last;}
   $s->bfloor();	
   $n = (sqrt($x*(8*$s-16) + ($s-4)**2)+$s-4) / (2*$s-4);
   if ($n == int($n)){print int($x)," is figurate at n = ",int($n),", s = ",int($s),"\n"; last;}
   $n->bceil();	
 }
}

it uses at most x^1/3 iterations to determine if x is non-fig where my algorithm, previously quoted, would use at most x iterations. So, it's far superior.

 

~modest

 

EDIT---->

 

here's Craig explaining his algorithm: http://scienceforums.com/topic/19130-non-figurate-numbers/page__view__findpost__p__291220

 

 

Don, as far as I know from peeking at the fine structure constant wiki page, the constant is known to about 10 significant digits. Right now, and someone can correct me if I'm wrong because I haven't been keeping up as much as I'd like to, the density of figurate numbers are known up to about 10 significant digits (I think about 100 billion). So, I'm wondering, if the density of a larger number of figs is found, how will you know that you've gotten any closer to the fine structure constant? As beta-x gets more accurate, or more precise, that won't necessarily tell you that you are any closer to alpha-x.

[phillip1882]

hey modest, i've never coded in perl before, so a bit of explaination would be helpful.

in particular what does the Math::BigFloat->new( a,b ) function do? i tried doing some google searching, but couldn't find much on this.

my guess would be declares a to b significant figures, but wanted to be sure.

[modest]

hey modest, i've never coded in perl before, so a bit of explaination would be helpful.

in particular what does the Math::BigFloat->new( a,b ) function do? i tried doing some google searching, but couldn't find much on this.

my guess would be declares a to b significant figures, but wanted to be sure.

 

You are correct. It declares a floating point with the initial value a to b digits of accuracy. Some of the other functions I call there, like bceil and bfloor are also in the bigfloat library.

 

http://perldoc.perl.org/Math/BigFloat.html

 

~modest