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

Sajan

Excel Ninja
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.
 

Luke M

Excel Ninja
@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...
 

SirJB7

Excel Rōnin
@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
 

Luke M

Excel Ninja
@Sajan and SirJB7

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

Sajan

Excel Ninja
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.
 

sameer bhide

New Member
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.....:)
 

jeffreyweir

Active Member
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
.
 

Luke M

Excel Ninja
@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.
 

jeffreyweir

Active Member
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.
 

Luke M

Excel Ninja
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
 

jeffreyweir

Active Member
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.
 

shrivallabha

Excel Ninja
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.
 

jeffreyweir

Active Member
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.
 

shrivallabha

Excel Ninja
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.
 

Luke M

Excel Ninja
@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.
 

shrivallabha

Excel Ninja
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.
 

jeffreyweir

Active Member
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 :)
 

Sajan

Excel Ninja
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.
 

jeffreyweir

Active Member
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
 

jeffreyweir

Active Member
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?
 

Sajan

Excel Ninja
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.
 

shrivallabha

Excel Ninja
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
 

Luke M

Excel Ninja
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:

shrivallabha

Excel Ninja
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
 
Top