• Hi All

    Please note that at the Chandoo.org Forums there is Zero Tolerance to Spam

    Post Spam and you Will Be Deleted as a User

    Hui...

  • When starting a new post, to receive a quicker and more targeted answer, Please include a sample file in the initial post.

Formula Challenge 006 - What's the largest number you can confirm is a prime?

Hi Jeff,

I am finding that this challenge requires more than my usual "couple of minutes here, couple of minutes there" type of attention I have been giving the other challenges! I am hoping to join the fray, and at least get an iron (or bamboo) medal! :)

But I have to first read up on primality testing...


-Sajan.
 
@Sajan


Glad to hear that it will take you some work as well. I would have been quite upset/jealous if you had solved this in < 1 hr. =P

Learned a lot from this about number theory, handling large numbers, MOD limitations...
 
@Luke M

Hi!

Regarding large numbers handle and operations with lots of digits (hundreds, thousands,...) which are usual in cryptography I once developed a workbook for the 4 basic operations, just to check if an example on Simon Singh's The Code Book was correct. And I now remember that I created another workbook for finding prime numbers and building a table... Where might they be? In what old computer disk... not so old, circa 2005 I guess. If I find them I'll post them here.

Regards!

http://www.nytimes.com/books/99/11/07/reviews/991107.07ossermt.html
 
@Sajan and SirJB7

Any luck on finding another method? I'm curious to see what other ways could be done.
 
Hi Luke,

No, nothing from me yet... I am still trying to read up on the AKS primality test, and while some of the sites describe it as easy, it still looks like Greek to me! (I suppose it would be easy if I were to implement it in something other than Excel.)


I will keep reading and trying as time (and motivation) permits!


-Sajan.
 
Folks,

I dont want to steal Jeff's thunder by posting the solution...but I am sure he wont mind if I give a small hint - No Rows*Tranpose(No Rows) is a very Large number.....:)
 
That's a heck of a bigger hint than my previous Use the grid, Sajan :)


In fact, I should have said Use the force, Luke.
 
@sameer

Good point, that would help shorten things possibly. However, the bigger problem I think is running out of resources/memory to do all the calculations in one shot.
 
Hi Luke. So what you need to do is only use the portion of the grid that you need to test for primality...not the whole grid.
 
Hence why I only use columns A:AE. Need to be able to generate the number 31,622,777 to test the biggest possible number within XL.


31,622,777 / 1,048,576 ~= 31


Not saying you have to do this, just explaining for other readers what my methodology/mad reasoning was. =P
 
What I meant is that to test say 17 you need a lot less of the grid than A:AE


My formula works out how much of the grid is needed, plus a tiny bit extra due to rounding.
 
I have Excel 2010 on win xp sp3 machine and it runs out of resources immediately. Here's possible conjecture as to what JW is holding up his sleeve.


Normally entered formula. For primes it should give value as 1 and the rest bigger than 1.


=SUMPRODUCT(--((A1/((ROW($A$1:INDEX(1:1048576,INT(SQRT(A1)/COLUMNS(1:1)),COLUMNS(1:1)))-1)+COLUMN($A$1:INDEX(1:1048576,INT(SQRT(A1)/COLUMNS(1:1)),COLUMNS(1:1)))))=INT(A1/((ROW($A$1:INDEX(1:1048576,INT(SQRT(A1)/COLUMNS(1:1)),COLUMNS(1:1)))-1)+COLUMN($A$1:INDEX(1:1048576,INT(SQRT(A1)/COLUMNS(1:1)),COLUMNS(1:1)))))))


To adjust rounding / sqrt errors a corrective buffer can be added to the rows portion.
 
My 153 character long formula dynamically constructs a 2d array that is just large enough to check if the particular number is a prime.


So:

If I’m checking 10, then my formula constructs this 2D array:

[pre]
Code: 
1	2
3	4
If I’m checking 100, then my formula constructs this 2D array:

[pre][code]1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16
If I’m checking 1000, then my formula constructs this 2D array:

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30
31	32	33	34	35	36
[/pre]
And if I’m checking 10000, then my formula constructs this 2D array:

1 2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 17 18 19 20 21 22
23 24 25 26 27 28 29 30 31 32 33
34 35 36 37 38 39 40 41 42 43 44
45 46 47 48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63 64 65 66
67 68 69 70 71 72 73 74 75 76 77
78 79 80 81 82 83 84 85 86 87 88
89 90 91 92 93 94 95 96 97 98 99
100 101 102 103 104 105 106 107 108 109 110
111 112 113 114 115 116 117 118 119 120 121[/code][/pre]
If you can work out how to produce these arrays, then you've all-but solved the challenge.


Note that these arrays are slightly longer than I need to check for primality. But only by a whisker.


Given that the size of the array corresponds to the size of the number I’m checking, small to medium numbers takes no time at all. Checking very large numbers – such as 122,816,065,582,079 – takes three to five seconds.


The biggest number I’ve managed to check so far is 202,005,700,000,123 but I often have to restart Excel to check the next number at that size.
 
I think, I have worked out a formula for grid and prime but Excel keeps giving me running out of resources error fairly quickly. The grid is useful way of generating numbers.


=SUM(--(MOD(A1,((ROW($A$1:INDEX(A:A,INT(SQRT(A1))))-1)*ROWS($A$1:INDEX(A:A,INT(SQRT(A1)))))+TRANSPOSE(ROW($A$1:INDEX(A:A,INT(SQRT(A1))))))=0))=1


Thanks to Jeff and Sameer's tip.
 
@shrivallabja

Not sure if this is the cause, but Jeff did point out a problem with the MOD function.

http://chandoo.org/forums/topic/formula-challenge-006-whats-the-number-you-can-confirm-is-a-prime-or-not#post-123502


It was messing me up earlier in my effort.
 
Yep, seems to be the case. Grid was larger than necessary in the previous post. Now


=SUM(--((A1/(((ROW($A$1:INDEX(A:A,INT(POWER(A1,0.25)+1)))-1)*ROWS($A$1:INDEX(A:A,INT(POWER(A1,0.25)))))+TRANSPOSE(ROW($A$1:INDEX(A:A,INT(POWER(A1,0.25)))))))=INT(A1/(((ROW($A$1:INDEX(A:A,INT(POWER(A1,0.25)+1)))-1)*ROWS($A$1:INDEX(A:A,INT(POWER(A1,0.25)))))+TRANSPOSE(ROW($A$1:INDEX(A:A,INT(POWER(A1,0.25)))))))))=1


Formula length is = 314


On my desktop it tests in this range: 50,995,137,249,401


then gives up.
 
Well done...you're getting there, but your formula fails on 15. Basically you need to make your array slightly bigger. For instance, for 15 your checking array is (1,2} whereas mine is ={1,2;3,4}


Note that you don't need INT, and you can replace POWER(p,0.25) with p^0.25 (and you could also use p^1/4 but then you'll have to put brackets around the 1/4 because otherwise Excel evaluates p^1 first, and then divides by 4. So no gain there.


And a shorter way of saying TRANSPOSE(ROW(... is COLUMN(...


Lastly, my formula was a bit longer than perhaps it needed to be because I had some IF statements in there handling 1 and 2. Without that, it's a slim 124 characters.


Let me know if you want to see it yet :)
 
Hi,


How about the following simplification of Shrivallabha's formula?

=SUM(N(ISERR(SEARCH("*.*",A1/((ROW(OFFSET(A$1,,,1+A1^0.25))-1)*INT(1+A1^0.25)+COLUMN(OFFSET(A$1,,,,1+A1^0.25)))))))=1


-Sajan.
 
Good skills, Sajan. Your revised method of creating the 'checking' array:

=(ROW(OFFSET(A1,,,1+p^0.25))-1)*INT(1+p^0.25)+COLUMN(OFFSET(A1,,,,1+p^0.25))

...is better optimised than mine:

=(ROW(OFFSET(A1,,,1+p^0.25))-1)*MAX(ROW(OFFSET(A1,,,p^0.25+1)))+(COLUMN(OFFSET(A1,,,,p^0.25+1)))


Note that you don't need the wildcards *.* around the period, and you can replace SEARCH with the shorter FIND:

=SUM(N(ISERR(FIND(".",p/((ROW(OFFSET(A$1,,,1+p^0.25))-1)*INT(1+p^0.25)+COLUMN(OFFSET(A$1,,,,1+p^0.25)))))))=1
 
So here's some I came up with a while back.

As per the above, you can't check the mod of any number over 2251799999999

But there's a workaround in the form of these:

=number-(INT(number/divisor)*divisor)

=MOD(MOD(number,134217728*divisor),divisor)


Here's two that uses those workarounds


=OR(p=3,p=5,AND((p-(INT(p/((ROW(OFFSET(A1,,,1+p^0.25))-1)*INT(1+p^0.25)+COLUMN(OFFSET(A1,,,,1+p^0.25))+1))*((ROW(OFFSET(A1,,,1+p^0.25))-1)*INT(1+p^0.25)+COLUMN(OFFSET(A1,,,,1+p^0.25))+1)))))


=OR(p=3,p=5,AND(MOD(MOD(p,134217728*((ROW(OFFSET(A1,,,1+p^0.25))-1)*INT(1+p^0.25)+COLUMN(OFFSET(A1,,,,1+p^0.25)))),1+((ROW(OFFSET(A1,,,1+p^0.25))-1)*INT(1+p^0.25)+COLUMN(OFFSET(A1,,,,1+p^0.25))))))


From memory they handles much larger numbers before Excel runs out of resources than the revision of shrivallabha's formula does. But haven't retested this.


Anyone care to do a comparison on their pcs and post back?
 
Hi Jeff,

One more optimization that could be done is to eliminate all of the even numbers using the ODD function. That would increase the range of numbers that could be checked.


-Sajan.
 
Few things:


1. Jeffrey's formula gives out of memory error as mine. So I think it is computer limitation than formula limitation. I am curious to know if it works on a better spec machine for higher numbers.


2. We have 16384 columns so it will put limitation [#REF error] at number greater than 72,057,594,037,927,900 but TRANSPOSE(ROW) wouldn't. That is why I chose TRANSPOSE.


3. If I do calculations using each formula then for 50,995,137,249,401 it takes following interval to calculate:

[pre]
Code: 
Jeffrey               2.78125
Sajan                 7.921875
Shrivallabha          3.15625
[/pre]
Post adopting some corrections it looks this [272 character long]:

=SUM(--((p/(((ROW($A$1:INDEX(A:A,INT(p^0.25+1)))-1)*ROWS($A$1:INDEX(A:A,INT(p^0.25)+1)))+TRANSPOSE(ROW($A$1:INDEX(A:A,INT(p^0.25)+1)))))=INT(p/(((ROW($A$1:INDEX(A:A,INT(p^0.25+1)))-1)*ROWS($A$1:INDEX(A:A,INT(p^0.25)+1)))+TRANSPOSE(ROW($A$1:INDEX(A:A,INT(p^0.25)+1)))))))=1
 
Despite being lengthy, I think I am still sitting pretty with my formula, which was able to handle the largest number capable of being analyzed in XL (999,999,999,999,999).


a) Do I think there's a shorter formula than can handle this large, AND be able to run on all machines? Yes

b) Am I perhaps a little proud of my accomplishment? Yes. :)
 
Last edited:
Luke,


The limit doesn't seem to be correct. Please check here:

http://office.microsoft.com/en-in/excel-help/excel-specifications-and-limits-HP005199291.aspx


It is 9.99999999999999E+307
 
You must log in or register to reply here.
Back
Top