A Truly Worthwhile Challenge.

[Kharakov]

Hi Phillip,

 

Well, as I said (in the post you got the code from) there is a simpler, more efficient algorithm for checking if number F is figurate,

 

F= number, r= rank

 

if [imath]2*(F-r)/(r^2-r) [/imath] is an integer F is figurate. Keep in mind that ALL integer values of [imath] r>= 3[/imath] are valid.

 

Now, as far as I can tell from your division algorithm (that you posted after your python version of my old code), you only check for values of r from 3 to 5, instead of values of r from 3 to ... however much you need)

 

array = [6,3,10,6,15,10]

 

With 6,3 corresponding to r=3;

10,6 corresponding to r=4;

15,10 corresponding to r=5;

 

Now while r=6 is accounted for by all r=3, which is probably why you stopped checking after r=5, you didn't account for:

 

r=7 which is only partially overlapped by r=4 and r=5

r=8 which is only partially overlapped by r=3 and r=4.. etc. etc.

 

so you have to run the check for ALL [imath]r>=3[/imath] such that [imath](F-r)*2 >= (r^2-r)[/imath]

 

Of course, if (r>3 && r % 3= 0) || ( r>4 && integerp([imath]sqrt®[/imath])) you don't have to check that rank of r as it has already been covered by a previous rank (AFAIK).

[phillip1882]

sorry i should comment my code.

#what this code does is start by calculating the number of unique values
#for rank 3, 4 and 5. then it checks each subsequent rank, 
#and if it add any new values, adds it to the list of ranks to check for overlap.

max = 10**8  #the maximum value
row = 28        #the current rank
column = 21    #the current rate at which the rank increases
rowinc = 7       #the value the rank initial value increases by. 
array = [6,3,10,6,15,10]  #the initial array
total = int((max-6)/3) +int((max-10)/6) +int((max-15)/10*2/3) +3 #the initial total for rank 3,4 and 5.
while row < max: #check to make sure current rank value less than the maximum value
   check = True  #used to determine whether there is compete overlap by a single other rank.
   for i in range(0,len(array),2): #check each rank, if complete overlap, then no further processing necessary. 
       if (row-array[i])%array[i+1] == 0 and column%array[i+1] == 0:
          check = False
          break
   if check:
       value = row  #value starts at the rank value ,and increments by column.
       print(row)     #this helps measure progression.
       while value<max:
           check = True  
           for i in range(0,len(array),2): #if the current value overlaps with any previous rank, don't increment total.
               if (value-array[i])%array[i+1] == 0:
                  check = False
                  break
           if check:
               total += 1
           value += column
       array += [row,column] #adds the current rank and increment to the array.
   column = row #get the next rank and increment amount
   rowinc += 1
   row += rowinc

print(total)

 

this code if you run it is actually pretty inefficient. i add many unnecessary ranks, such as 55,45 to the array for checking. i might modify my code so the equation more resembles your own code, though I'm not quite sure how yet. i just ran the code and it correctly gets the value for 10**8 in 190 seconds. but i think it could be faster.

[Kharakov]

Nice. I'm going to try and implement it in maxima later (not sure if I have time tonight). Let you know how it turns out. Decided not to, actually... more at bottom of post.

 

You are generating each rank and eliminating overlaps with previous ranks, which is really nice (instead of checking through all the ranks for each number until you get a hit). Your method avoids checking through the ranks (up to rmax, or in your case, max) for non-figurate numbers. Much more efficient than checking every single number (as I was doing).

 

I don't know if you care, but:

 

r= current rank number p= previous ranks increment

 

For n= 1 to ...

 

rank1 = r + [0] * n

rank2 = r + [p+(r-1)] * n // we don't take into account rank 1 and 2, but they exist

rank3 = r + [p+(r-1)] * n

rank4 = r + [p+(r-1)] * n

rank5 = r + [p+(r-1)] * n

rank6 = r + [p+(r-1)] * n

rank7 = r + [p+(r-1)] * n

 

I also am not sure if using the modulus function in python is more efficient than checking if a number is an integer? x % y usually does x - y * floor(x/ y) when you can just check if x/y is an integer (instead of the subtraction and multiplication).

 

What python distribution are you using, if you don't mind me asking?

 

 

more|| The point being, your method is great for generating numbers. So now, we need an exact percentage generator, which checks rank contributions (or n-gon contributions), towards total percentage. I can tell you already pursued this path a bit, by the "total" number in your script.

 

I went up it a bit further, up to rank 17, and developed various maxima scripts to explore the functions, but have decided python will be better based on the array commands I've seen you use. Anyway, the rank overlap gets more complicated the higher in rank we go: 7 overlaps with 5 and 4; 8 with 3 and 4; 11 with 8,7,4, and 3 so we get some overlaps of the overlaps; 13 is even worse...

 

Now to check rank overlaps is pretty simple (you've been doing it).

integerp((high_start-low_start+high_gap*i)/(low_gap))

 

OR with % (mod)

 

(high_start-low_start+ high_gap*i) % low_gap = 0

 

Now you can check this a certain number of i, and after the first hit you start a counter on the next i until the next hit, and determine the fractional part to be 1/ (counter). Save the starting numeric value of the first hit (when 11 hits 8), and when you get the next hit you've got your gap (2nd hit - 1st hit = gap). Do the same thing with when 11 hits 7. Then 11 hits 4, and 11 hits 3. Save all values in an array (fractional hit proportion, starting value, gap).

 

Then calculate the subhits: 11,8 hits 11,7??? no 11,8 hits 11,4??? yes. Calculate fraction to subtract from 11,8's total fraction. 11,8 hits 11,3??? yes. Calculate fraction to subtract from 11,8's total fraction.

 

And if you were up in rank 17, you'd have to do sub hits of sub hits of sub hits.... so I'm thinking that as long as a rank has subranks below the current testing level, we need to implement a new array to calculate total fractions.

[Don Blazys]

You guys are working hard.

 

I would like to buy you all a round of drinks, but we are not at a bar or club... so I will tell you a joke instead.

 

 

 

If former vice president Al Gore was a drummer, then what kind of rythym would he be playing ?

 

An "Al Gore rythym" ... of course!

 

 

And from this day forward, every time you say, hear, read or even think the word "algorithm",

 

(which will be quite often, since you guys are coders) you will remember this joke and smile. :D

 

Just remember...

 

Al Gore rythym...

 

algorithm...

 

Al Gore rythym...

 

algorithm...

 

Al Gore rythym...

 

algorithm...

 

Just remember...

 

 

 

Don.

[phillip1882]

hey kharakov,

I don't know if you care, but:

 

r= current rank number p= previous ranks increment

 

For n= 1 to ...

 

rank1 = r + [0] * n

rank2 = r + [p+(r-1)] * n // we don't take into account rank 1 and 2, but they exist

rank3 = r + [p+(r-1)] * n

rank4 = r + [p+(r-1)] * n

rank5 = r + [p+(r-1)] * n

rank6 = r + [p+(r-1)] * n

rank7 = r + [p+(r-1)] * n

 

ah a good observation, though i knew this implicitly, i didn't really implement it, i should. this will eliminate some storage.

I also am not sure if using the modulus function in python is more efficient than checking if a number is an integer? x % y usually does x - y * floor(x/ y) when you can just check if x/y is an integer (instead of the subtraction and multiplication).

unfortuately, division in python automatically makes a number a float.

Now you can check this a certain number of i, and after the first hit you start a counter on the next i until the next hit, and determine the fractional part to be 1/ (counter). Save the starting numeric value of the first hit (when 11 hits 8), and when you get the next hit you've got your gap (2nd hit - 1st hit = gap). Do the same thing with when 11 hits 7. Then 11 hits 4, and 11 hits 3. Save all values in an array (fractional hit proportion, starting value, gap).

 

Then calculate the subhits: 11,8 hits 11,7??? no 11,8 hits 11,4??? yes. Calculate fraction to subtract from 11,8's total fraction. 11,8 hits 11,3??? yes. Calculate fraction to subtract from 11,8's total fraction.

 

And if you were up in rank 17, you'd have to do sub hits of sub hits of sub hits.... so I'm thinking that as long as a rank has subranks below the current testing level, we need to implement a new array to calculate total fractions.

right, i didn't persue this path because it seems overly complex, but it might give us a much better value for w(x).

 

What python distribution are you using, if you don't mind me asking?

i'm using 3.1, but 2.7 isnt much different. only the print and raw input functions change, and a few other small modifications. array handling works the same, so if your used to 2.7 i'd recomend sticking to that.

[Kharakov]

unfortuately, division in python automatically makes a number a float.

ohh well...

right, i didn't persue this path because it seems overly complex, but it might give us a much better value for w(x).

It would give us a precise fractional value, although it borders on exponentially complicated as we proceed through the ranks. Rank 100 has 40+ sub ranks (maybe only 30+?), all of which have to be checked against all ranks below them, with each needing to be checked versus the ranks below them..... bleh.

 

I did notice that the rank totals drop off rapidly:

r3: 1/3

r4: 1/6

r5: 1/15 (skip ranks that have no influence, like 6,9,10,12,15,16.....)

r7: 2/105

r8: 1/84

r11: 13/1155

r13: 43/5005 <--might be wrong, screwed up the script prior to calc and didn't check after I fixed it

r14: 43/15015

r17: 34549/10125115

 

All added up we get 25261833/40500460: 62.37 %... which is still pretty far from the total 64% +

I did notice that the factors in the fraction seems to preserve the rank prime numbers (although some are canceled out in the division process).

40500460: 2^2 5 7^2 11 13 17^2 Although the 3s canceled out...

 

i'm using 3.1, but 2.7 isnt much different. only the print and raw input functions change, and a few other small modifications. array handling works the same, so if your used to 2.7 i'd recomend sticking to that.

Not used to either, but I really like the syntax (from your code that I've read), so was wondering which way to go. I'll go with 3.1+, as it's the format that people will be using in the future (I assume), and our code should be compatible then.

[phillip1882]

Not used to either, but I really like the syntax (from your code that I've read), so was wondering which way to go. I'll go with 3.1+, as it's the format that people will be using in the future (I assume), and our code should be compatible then.

good idea. yeah i enjoy programming in python, readable code, easy to understand, can do alot with a little. my only complaint is that white space dermines block level, so if you don't write neatly spaced code, it won't run. this can be a nucance while writing code, but after you get it to run succefully, your glad you went though that small headache later on. i'd recommend cream as a python text editor.

[Kharakov]

good idea. yeah i enjoy programming in python, readable code, easy to understand, can do alot with a little. my only complaint is that white space dermines block level, so if you don't write neatly spaced code, it won't run. this can be a nucance while writing code, but after you get it to run succefully, your glad you went though that small headache later on. i'd recommend cream as a python text editor.

Thanks Phillip. I'll check it out.

 

I've got an idea for the percentage calculation thing. Not sure if it will work, but... if we can determine the length of one full cycle (which includes all overlaps) we wouldn't have to search for all of the overlaps of overlaps.

 

One idea is to find the cycle of greatest length, for say rank 14's subrank overlaps. So we have 14 intersecting with 11 every 55 hits (polygons), starting at the 34th polygon of rank 14. So, we should find a fraction that comes up again and again, every full_cycle_count * 55 that is the actual rank 14 total. I'll have to dig through my old messy scripts from a few weeks ago, but to find when rank 14 intersects with rank 11 you take

 

(rank 14 starting point- rank 11 starting point + rank 14 increment )/ rank 11 increment..

 

then from that starting point (34th might be 32?? poly I think) you start a count until the next hit (which is 55 away). Anyways, we just have to look for a fraction that keeps on popping up from the first 11 hit to some multiple of 55 away. Basically, 11 is going to go through a complex cycle of hits on lower orders (7,4, and 3 in this specific case) that repeats itself, repeats itself. <-- yeah

 

Of course, I don't know for sure what the cycle is... So there is a bit of work to do. Maybe, just maybe, finding how the cycles work will be more efficient than the exponentially complicated recursive rank checking.... We can do the first 20 or so by hand, just to check against our algorithm.

[phillip1882]

so far, i've found 18 to be a good base cycle length, as i demonstrated in an earlier post.

rank 3 will add 6 bits.

rank 4 will add 3 bits.

rank 5 will add 2 bits.

in 126 (18*7) rank 7 will add 2 bits.

in 252 (126*2) rank 8 will add 2 bits.

this is as far as i've gone by hand, so perhaps it's time to add some computer power to the mix.

[Kharakov]

so far, i've found 18 to be a good base cycle length, as i demonstrated in an earlier post.

rank 3 will add 6 bits.

rank 4 will add 3 bits.

rank 5 will add 2 bits.

in 126 (18*7) rank 7 will add 2 bits.

in 252 (126*2) rank 8 will add 2 bits.

this is as far as i've gone by hand, so perhaps it's time to add some computer power to the mix.

I don't really get what you mean. I was noticing that cycle lengths seemed to increase with increasing rank overlaps.

 

Ohh, and phillip, here is Donk's algorithm from a long time ago that works a lot better than checking through the ranks (apparently, havent tested it, although I assume testing a few factors is better than testing all ranks).

[phillip1882]

list all numbers between 1-18, mark the figurate numbers.

then between 18-36, mark the figurate numbers of rank 3,4 and 5.

if you keep increasing by a value of 18 and do ranks 3,4,5 you notice the pattern of marks repeats precisely.

go up to 144. mark the unique values of 21n+28. if you do another 126, (144-18 = 126)the pattern repeats precisely.

go up to 270. mark the unique values of 28n+36. if you do another 252, (270-18 = 252)the pattern repeats precisely.

i hope this clears up the confusion.

[Kharakov]

list all numbers between 1-18, mark the figurate numbers.

then between 18-36, mark the figurate numbers of rank 3,4 and 5.

if you keep increasing by a value of 18 and do ranks 3,4,5 you notice the pattern of marks repeats precisely.

go up to 144. mark the unique values of 21n+28. if you do another 126, (144-18 = 126)the pattern repeats precisely.

go up to 270. mark the unique values of 28n+36. if you do another 252, (270-18 = 252)the pattern repeats precisely.

i hope this clears up the confusion.

Looks promising. Wondering about the initial hits, and how exactly the step progression works (from rank 7 to rank 8 it doubles, but from 5 to 7 it multiplies by 7).

 

I did a quick maxima run of Donk's algorithm. It runs pretty fast. Don't know how it compares to yours however.

[Kharakov]

Allright. So I wrote a maxima script (still more familiar with it, will get into python at some point) to set either 1 or 0 to each position. Then I wrote a script to add up positions, to check the pattern... and I think I found it.

 

The pattern for ranks 3 and 4 starts at 3*4. Every 3*4 it repeats. (6 hits every 12 numbers= 1/2 )

The pattern for ranks 3,4 and 5 starts at 3*4*5. Every 3*4*5 it repeats. (34 hits every 60 numbers= 17/30)

The pattern for 3,4,5,7 starts at 3*4*5*7, repeats the same. (236 hits every 420 = 41 / 70)

 

So we now have a method for checking ranks EXACTLY. Should end up with 251/420 for rank 8... gonna check it now...

 

Something I noticed about the pattern: if you only include all of the factors of the rank once it seems to work. But.. we should check.

 

For rank 8 I think you only need to multiply by 2 because 4 is already in the mix.

 

Yup. It worked, got 502/840 for rank 8, which I already calculated (the hard way) earlier as 251/420 (which is the same as 502/840).

 

Rank 11 got 5600/9240 repeating... so thats 20/33.

 

 

Ok... so you can drop out even factors once. You only need to have 4 in for rank 8, and I'm assuming it has something to do with that whole "divided by 2" part of the generating function.

 

That means you've gotta check less to check the ranks (so to check 2 loops for 11, you only need (3*4*5*7*11) *3 checked if figurate), then you add up from (3*4*5*7*11) to (3*4*5*7*11)*2-1 and (3*4*5*7*11)*2 to (3*4*5*7*11)*3-1 to make sure they match.

 

If you get a match, you take that number / (3*4*5*7*11) and this is your fraction...

 

The amount you have to check rapidly adds up, 180180 at rank 13... and you gotta keep on increasing it. While we do get an exact value for all ranks via this method, we need to find a way to do it with much less checks. The following scripts are a rewrite to do a single check, assuming that the method is correct. *** I haven't verified it, but in the non-fig thread I stated that I believe the factors of the rank increment (21=7*3 for rank 7, 28= 2*2*7 for rank 8, which makes sense since we only use a 4 multiplier for that rank, rank 14 doesn't need more factors as it's factors are already covered 7*13=91).

 

We can run 2 checks (starting checking distance apart) if we want to verify the formula for higher ranks. Don't know if it is necessary.

 

here are the various scripts, they all work together (call one another):

ffp(f):=[
z:(divisors(f)),      //gives you a list of all divisors of f
ff:listify(z),           // well, this puts it into list format so I can access specific numbers
zlength:length(ff)   //this is like len(array) gives you the length of a list
]$
zlength:0$ zclength:0$    //gotta initialize these variable Before you run the following scripts because I call them... 

countf(f,maxn):=               // this script is called by the loop script below to calculate whether a number is figurate
[ffp(f*2),testpass:false,              
for i:1 thru (zlength) do  [      
n:ff[i],                                    //  ff[i] gives us the divisors of f we calculated with ffp(f)
if n>2 and n<f and n<=maxn then [                // maxn is the highest polygon tested  weird that this works as it's not the rank????
s:(2*n^2-4*n+2*f)/(n^2-n),                           //  this is my implementation of Donk's checking method, you can check however you like
if integerp(s) and s>2 and s#f then testpass:true ]],
if testpass then [countf:countf+1,totalcount:totalcount+1] else    // count up yer figs...
totalcount:totalcount+1
]$

countfloop (lowf,highf,maxn):=[                    // loop to count from lowf to highf with maxn being the highest polygon you check for
sert:elapsed_real_time(),totalcount:0,countf:0,     // weirdly enough, maxn corresponds to the highest rank... or maybe I'm a nut...
for f:lowf thru highf do 
countf(f,maxn),
disp(sconcat("  Total fraction: ",countf/totalcount)),
tert:elapsed_real_time()-sert,
disp(sconcat(" Calculation Time: ",tert))]
$

I call it this way:
countfloop(2*6*5*7,2*7*6*5*2-1,8);       //2*6*5*7 is the starting point of rank 8's loop   2*6*5*7*2-1 is the end of it, and 8's the rank yo

it outputs:
 Total fraction: 251/420
Calculation Time: 0.11000000000058

 Here is rank 11:  (had to calculate 13* as much... and check more n... )
 Total fraction: 20/33
Calculation Time: 1.860000000000582

Here is rank 13:
 Total fraction: 839/1365
Calculation Time: 29.75    <--  almost 30 seconds... it's increasing fast....

I'll run rank 14 while I  go get a bite to eat, but I think I'll stop there for now.

Here is rank 14:
 Total fraction: 1237/2002
Calculation Time: 520.9499999999971     // 8 minutes 41 seconds..  the next rank, 17, will be a lot more

[phillip1882]

unfortunately, not sure that works.

rank 22 for example adds new values to the mix, while rank 16 does not.

[Kharakov]

unfortunately, not sure that works.

rank 22 for example adds new values to the mix, while rank 16 does not.

Hey Phillip, been doing a 3d Mandelbrot formula over at fractalforums so I missed your reply. Anyways-

 

It works, checked it by adding in the intersecting ranks (such as 9,6,10, etc.), and it adds nothing for them (which makes sense).

 

You need to consider that it only checks whether a number is included, not what rank adds it, so if an earlier rank adds the number, it won't check it again (so for rank 16, which is covered by rank 4 (I believe), it doesn't add anything in when calculating fractions).

 

It does more or less (pseudo) exponentially increase in amount of calculations needed as we increase ranks, which limits the formula's use (until quantum computers are as common as cellphones).

[Don Blazys]

Here's an idea.

 

I work at a high school, and am friends with some of the teachers in

the science, mathematics and computer departments.

I might be able to talk one of them into conducting an "experiment"

whereby an older, out of use computer is programmed to count the

non-trivial polygonals and simply left running, day after day,

week after week, month after month, year after year...

well, you get the picture.

 

Here are some questions that I hope you can answer.

 

1) How much "extra memory" would the computer require,

and can such extra memory be purchased for a reasonable price?

 

2) How long would it take to get to [math]\varpi(10^{13})[/math]

using, say, a "Dell Optiplex 760" ?

 

3) Would the above mentioned computer (or a similar model)

"overheat" or otherwise "suffer" if left running continuously

for a very long period of time?

Would it need to "rest" periodically, and if so,

would such rest periods be possible without losing or somehow

"corrupting" all the data and information previously gathered?

 

4) Would anyone in this forum be willing to work with

one of our teachers and help him or her with the coding,

programming and other essentials and details necessary

to get such a project started, sustained and maintained?

 

5) Are there any other important considerations that

need to be taken into account before I consider

approaching some of our staff with such a project?

 

Don.

[phillip1882]

hey don,

1) it depends on the algorithm. you could modify mine slightly to not use very much memory at all.

2) assuming the latest one (core 2 duo) on my pc, Pentium 4, it got to 10^8 in 190 seconds, the core 2 duo is roughly 80% faster, so assuming 10^13 took 19,000,000 seconds, or 213 days, the core 2 duo would take 43 days.

3) probably not, computers are well designed for heat generally, as long as you have good air flow.

4) sure, I'd love to.

5) just to let you know i am getting a pretty beefy CPU for Christmas, so such a project may be unnecessary.