Puzzling Primes

Page 1 of 1 [ 13 posts ]

Joined: 31 Aug 2012
Gender: Male
Posts: 10,660
Location: In the heart of the dust bowl

05 Apr 2013, 1:20 pm

[img][652:423]http://img.spikedmath.com/comics/374-puzzling-primes.png[/img]

I haven't done it yet, but I suspect that the result is going to be quite a large number.

ruveyn
Veteran
Veteran

Joined: 21 Sep 2008
Age: 87
Gender: Male
Posts: 31,502
Location: New Jersey

05 Apr 2013, 2:51 pm

Wait. How do we know this only leaves a single number. You might be left with several non primes none of which are crossed out and replaced by there sum plus their product.

eric76
Veteran
Veteran

Joined: 31 Aug 2012
Gender: Male
Posts: 10,660
Location: In the heart of the dust bowl

05 Apr 2013, 3:06 pm

You just keep going until they are all gone.

For example, if it was up to 10, you would start with 2,3,5,and 7. Suppose you pick 2 and 5. Then 2+5+2*5 = 17. Remove the 2 and 5 and write down 17 and you get 3, 7, and 17.

Then pick two numbers, say 17 and 3. 3+17+3*17=71. Remove the 3 and 17 and you have 7 and 71. Pick these two numbers and you get 7 + 71 + 7*71 = 575.

So as long as you have two numbers on the board, you can combine them in this way.

By the way, that site has some pretty good cartoons: http://spikedmath.com/488.html

jellybaby
Butterfly

Joined: 5 Apr 2013
Age: 25
Gender: Female
Posts: 16

07 Apr 2013, 7:57 pm

Im going to do this tomorrow. There are 168 prime numbers (i think...) between 1 and 1000. I would do it now but it is 2am and it will give me something to do at school tomorrow.

I do think however that the answer will be x+y+(x*y) where x=y because 575 is 23+23+(23*23)

Last edited by jellybaby on 07 Apr 2013, 8:19 pm, edited 1 time in total.

ModusPonens
Veteran
Veteran

Joined: 1 Jan 2013
Age: 40
Gender: Male
Posts: 715

07 Apr 2013, 8:14 pm

jellybaby wrote:

Im going to do this tomorrow. There are 168 prime numbers (i think...) between 1 and 1000. I would do it now but it is 2am and it will give me something to do at school tomorrow.

Please write a computer programme to do it! It's barbaric to do it manualy!

jellybaby
Butterfly

Joined: 5 Apr 2013
Age: 25
Gender: Female
Posts: 16

07 Apr 2013, 8:32 pm

ModusPonens wrote:

jellybaby wrote:

Im going to do this tomorrow. There are 168 prime numbers (i think...) between 1 and 1000. I would do it now but it is 2am and it will give me something to do at school tomorrow.

Please write a computer programme to do it! It's barbaric to do it manualy!

I would only have to do ....167 sums

Okay yeah ill make a number machine in excel.

eric76
Veteran
Veteran

Joined: 31 Aug 2012
Gender: Male
Posts: 10,660
Location: In the heart of the dust bowl

07 Apr 2013, 10:12 pm

An old friend of mine in graduate school who was quite brilliant had an approach to solving problems that was unusual for most students. He would set the problem up and work it to the point that only an arithmetical calculation was required to come up with the answer. Instead of working out that arithmetical calculation, he would stop at that point and write down something like "the remaining steps are nothing but minor arithmetic" and go on to the next problem.

morslilleole
Veteran
Veteran

Joined: 17 Dec 2011
Age: 35
Gender: Male
Posts: 511
Location: Norway

08 Apr 2013, 10:09 am

I quickly made a program that would calculate the answer for the first two numbers remaining and add the result to the correct position in the list ( keeping it sorted at all times. )

I ended up with the following

Code:

result of 2 and 3 is 11
result of 5 and 7 is 47
result of 11 and 11 is 143
result of 13 and 17 is 251
result of 19 and 23 is 479
result of 29 and 31 is 959
result of 37 and 41 is 1595
result of 43 and 47 is 2111
result of 47 and 53 is 2591
result of 59 and 61 is 3719
result of 67 and 71 is 4895
result of 73 and 79 is 5919
result of 83 and 89 is 7559
result of 97 and 101 is 9995
result of 103 and 107 is 11231
result of 109 and 113 is 12539
result of 127 and 131 is 16895
result of 137 and 139 is 19319
result of 143 and 149 is 21599
result of 151 and 157 is 24015
result of 163 and 167 is 27551
result of 173 and 179 is 31319
result of 181 and 191 is 34943
result of 193 and 197 is 38411
result of 199 and 211 is 42399
result of 223 and 227 is 51071
result of 229 and 233 is 53819
result of 239 and 241 is 58079
result of 251 and 251 is 63503
result of 257 and 263 is 68111
result of 269 and 271 is 73439
result of 277 and 281 is 78395
result of 283 and 293 is 83495
result of 307 and 311 is 96095
result of 313 and 317 is 99851
result of 331 and 337 is 112215
result of 347 and 349 is 121799
result of 353 and 359 is 127439
result of 367 and 373 is 137631
result of 379 and 383 is 145919
result of 389 and 397 is 155219
result of 401 and 409 is 164819
result of 419 and 421 is 177239
result of 431 and 433 is 187487
result of 439 and 443 is 195359
result of 449 and 457 is 206099
result of 461 and 463 is 214367
result of 467 and 479 is 224639
result of 479 and 487 is 234239
result of 491 and 499 is 245999
result of 503 and 509 is 257039
result of 521 and 523 is 273527
result of 541 and 547 is 297015
result of 557 and 563 is 314711
result of 569 and 571 is 326039
result of 577 and 587 is 339863
result of 593 and 599 is 356399
result of 601 and 607 is 366015
result of 613 and 617 is 379451
result of 619 and 631 is 391839
result of 641 and 643 is 413447
result of 647 and 653 is 423791
result of 659 and 661 is 436919
result of 673 and 677 is 456971
result of 683 and 691 is 473327
result of 701 and 709 is 498419
result of 719 and 727 is 524159
result of 733 and 739 is 543159
result of 743 and 751 is 559487
result of 757 and 761 is 577595
result of 769 and 773 is 595979
result of 787 and 797 is 628823
result of 809 and 811 is 657719
result of 821 and 823 is 677327
result of 827 and 829 is 687239
result of 839 and 853 is 717359
result of 857 and 859 is 737879
result of 863 and 877 is 758591
result of 881 and 883 is 779687
result of 887 and 907 is 806303
result of 911 and 919 is 839039
result of 929 and 937 is 872339
result of 941 and 947 is 893015
result of 953 and 959 is 915839
result of 967 and 971 is 940895
result of 977 and 983 is 962351
result of 991 and 997 is 990015
result of 1595 and 2111 is 3370751
result of 2591 and 3719 is 9642239
result of 4895 and 5919 is 28984319
result of 7559 and 9995 is 75569759
result of 11231 and 12539 is 140849279
result of 16895 and 19319 is 326430719
result of 21599 and 24015 is 518745599
result of 27551 and 31319 is 862928639
result of 34943 and 38411 is 1342268927
result of 42399 and 51071 is 2165452799
result of 53819 and 58079 is 3125865599
result of 63503 and 68111 is 4325384447
result of 73439 and 78395 is 5757402239
result of 83495 and 96095 is 8023631615
result of 99851 and 112215 is 11204992031
result of 121799 and 127439 is 15522191999
result of 137631 and 145919 is 20083261439
result of 155219 and 164819 is 25583360399
result of 177239 and 187487 is 33230373119
result of 195359 and 206099 is 40263695999
result of 214367 and 224639 is 48155627519
result of 234239 and 245999 is 57623039999
result of 257039 and 273527 is 70307637119
result of 297015 and 314711 is 93474499391
result of 326039 and 339863 is 110809258559
result of 356399 and 366015 is 130448102399
result of 379451 and 391839 is 148684471679
result of 413447 and 423791 is 175215954815
result of 436919 and 456971 is 199660206239
result of 473327 and 498419 is 235916141759
result of 524159 and 543159 is 284702745599
result of 559487 and 577595 is 323158030847
result of 595979 and 628823 is 374766527519
result of 657719 and 677327 is 445492172159
result of 687239 and 717359 is 492998486399
result of 737879 and 758591 is 559749864959
result of 779687 and 806303 is 628665553151
result of 839039 and 872339 is 731928153599
result of 893015 and 915839 is 817859773439
result of 940895 and 962351 is 905473147391
result of 990015 and 3370751 is 3337098412031
result of 9642239 and 28984319 is 279473769676799
result of 30417151 and 75569759 is 2298616876523519
result of 140849279 and 247726079 is 34892040005222399
result of 326430719 and 518745599 is 169334499704831999
result of 570425343 and 862928639 is 492236366319452159
result of 910987263 and 1035483647 is 943312415408259071
result of 1104372767 and 1234904063 is 1363794419374129151
result of 1342268927 and 1404116479 is 1884701922396733439
result of 1462434943 and 1588160383 is 2322581242238058495
result of 1599083519 and 1600327935 is 2559058029053214719
result of 223608831 and 1608990335 is 359784449732247551
result of 33554431 and 1783713279 is 59851485961256959
result of 1788465151 and 1815987199 is 3247829823678054399
result of 1396703231 and 1919311871 is 2680709094838370303
result of 2037678079 and 2091710623 is 4262232888227921919
result of 18446744071580037119 and 18446744071815823359 is 4032721772636798975
result of 18446744071857094655 and 18446744072029641759 is 3111960704919797759
result of 18446744072051874431 and 18446744072070167935 is 2717568922157957119
result of 1373487103 and 18446744072317976575 is 16535433702021267455
result of 18446744072366587903 and 18446744072525124991 is 1590641975558668287
result of 18446744072540449919 and 18446744072580186367 is 1320342826840260607
result of 931954687 and 18446744072694770495 is 17501014051631661055
result of 1017118719 and 18446744072716550143 is 17436743687550795775
result of 18446744072786798975 and 18446744072831847295 is 809903978419404799
result of 18446744071962443775 and 18446744072849660479 is 1502322545252106239
result of 802160639 and 18446744072944599551 is 17833129636481990655
result of 18446744072098938879 and 18446744073048948735 is 1063975411966279679
result of 18446744073143248639 and 18446744073402492095 is 173888719985131519
result of 18446744071984201727 and 18446744073441116159 is 463145083944828927
result of 18446744073503506431 and 18446744073523108239 is 38415759713501183
result of 260046847 and 18446744073618374655 is 18423033792651329535
result of 18446744073675997183 and 18446744073709551615 is 18446744073709551615
result of 18446744073709551615 and 18446744073709551615 is 18446744073709551615
result of 18446744073709551615 and 18446744073709551615 is 18446744073709551615
result of 18446744073709551615 and 18446744073709551615 is 18446744073709551615
result of 18446744073709551615 and 18446744073709551615 is 18446744073709551615
result of 18446744073709551615 and 18446744073709551615 is 18446744073709551615
result of 18446744073709551615 and 18446744073709551615 is 18446744073709551615
result of 18446744073709551615 and 18446744073709551615 is 18446744073709551615
Printing list....
18446744073709551615

Assuming I haven't made any mistakes ( which I probably have =P ) the numbers will exceed ( 2 ^ 64) - 1, which is the maximum value that can be represented with by 8 bytes.

graywyvern
Veteran
Veteran

Joined: 2 Aug 2010
Age: 66
Gender: Male
Posts: 666
Location: texas

08 Apr 2013, 11:34 am

this is beautiful

_________________
"I have always found that Angels have the vanity
to speak of themselves as the only wise; this they
do with a confident insolence sprouting from systematic
reasoning." --William Blake

eric76
Veteran
Veteran

Joined: 31 Aug 2012
Gender: Male
Posts: 10,660
Location: In the heart of the dust bowl

08 Apr 2013, 2:38 pm

morslilleole wrote:

Assuming I haven't made any mistakes ( which I probably have =P ) the numbers will exceed ( 2 ^ 64) - 1, which is the maximum value that can be represented with by 8 bytes.

According to ModusPonens, there are 168 prime numbers between 1 and 1000. Even if you merely just multiplied those prime numbers together without adding anything in there, it's going to greatly exceed 2^168.

If I remember correctly, Lisp can handle as large a number as is necessary. Does anyone know Lisp? (I had a very brief introduction to it, but promptly forgot it all.)

ScrewyWabbit
Veteran
Veteran

Joined: 8 Oct 2008
Gender: Male
Posts: 1,154

08 Apr 2013, 5:54 pm

The .NET languages (C# / VB.NET) have a BigInteger class in the System.Numeric library - this allows integers to be stored and math operations on them, where the size of the integer in theory has no upper limit - of course memory is finite so that entails some sort of finite upper limit on the size. In any case, working with these objects is slower since ultimately arithmetic operations using them are not single math operations in the CPU, but lengthier compound operations. I think Java has something similar IIRC.

Assuming a brute-force, exhaustive check of every possibility, the difficulty with this problem on a desktop PC is simply going to be processing time, I think. If there are 168 prime numbers below 1000, to start you have to chose two of those 168 to perform the first operation and reduce your list of numbers to 167. Then you chose two of the 167, then two of the 166, etc. In my probability class in college, we used to call this "n choose y" - i.e. from a set of n items, how many ways can I chose y of them (where x >= y). The formula for this is x! / [(x-y)! * y!]...

So in this case, we have 168 choose 2, multiplied by 167 choose 2, multiplied by 166 choose 2 - and so on until 2 chose 2. That is a truly massive number and the resulting "Q" would have to be computed for every single one of these possibilities.

So maybe there's a way to do this without a brute force check of every possibility - maybe it could be proven that the two smallest primes should be replaced first, and then at every step the two smallest remaining numbers should be the ones to be replaced. I've no idea, however, if that would really give the minimum value for Q, or not.

eric76
Veteran
Veteran

Joined: 31 Aug 2012
Gender: Male
Posts: 10,660
Location: In the heart of the dust bowl

08 Apr 2013, 6:44 pm

ScrewyWabbit wrote:

So maybe there's a way to do this without a brute force check of every possibility - maybe it could be proven that the two smallest primes should be replaced first, and then at every step the two smallest remaining numbers should be the ones to be replaced. I've no idea, however, if that would really give the minimum value for Q, or not.

The first thing to do is to try by hand on small sets, look for patterns, and try to generalize.

ScrewyWabbit
Veteran
Veteran

Joined: 8 Oct 2008
Gender: Male
Posts: 1,154

09 Apr 2013, 2:37 pm

eric76 wrote:

ScrewyWabbit wrote:

The first thing to do is to try by hand on small sets, look for patterns, and try to generalize.

Actually, thinking about it some more, the correct approach for each iteration might be to choose the smallest remaining number for x, and the largest remaining number for y. This would minimize the impact of the larger numbers on the eventual value of Q - since leaving the larger numbers for the end means they're going to be multiplied together, maximizing their impact. Multiplying them with the smallest possible numbers would minimize their impact. In any case, however I don't think there's a provable approach that's guaranteed to get the minimum result without a brute force check of all possibilities - I don't think for instance that there's a mathematical way to prove one way is better than another - at least with an arbitrary set of non-duplicating positive integers, even within a given range as in this case. That the numbers are primes I don't think makes a big difference either.

Page 1 of 1 [ 13 posts ]

Jump to:

Puzzling Primes Post Reply New Topic

Puzzling Primes