CR4® - The Engineer's Place for News and Discussion®

Challenge Questions Blog

### Challenge Questions

So do you have a Challenge Question that could stump the community? Then submit the question with the "correct" answer and we'll post it. If it's really good, we may even roll it up to Specs & Techs. You'll be famous!

Answers to Challenge Questions appear by the last Tuesday of the month.

 Previous in Blog: Tropical Sun: Newsletter Challenge (February 2017) Next in Blog: Answer: Prime Partition, March 2017 Challenge Question

# Puzzling Prime Partition: Newsletter Challenge (March 2017)

Posted February 28, 2017 5:01 PM

This month's Challenge Question: Specs & Techs from IEEE Engineering360:

If p(n) is the number of partitions of n, defined as the number of ways to write the integer n as a sum of positive integers where the order of the addends is not significant, what n produces the 42nd largest prime p(n)?

The answer to this challenge will be posted later this month, right here on CR4.

Interested in this topic? By joining CR4 you can "subscribe" to

Check out these comments that don't yet have enough votes to be "official" good answers and, if you agree with them, rate them!
Guru

Join Date: Mar 2007
Location: at the beach in Florida
Posts: 19472
#1

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

02/28/2017 7:36 PM

225,964,951-1

__________________
Life is like riding a bicycle. To keep your balance you must keep moving. A.E.
Guru

Join Date: Dec 2016
Posts: 2914
#3

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

02/28/2017 10:43 PM

I do not think this problem is speaking of Mersenne primes.

Guru

Join Date: Mar 2007
Location: at the beach in Florida
Posts: 19472
#4

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

02/28/2017 11:02 PM

Then it would be ....749474411781

__________________
Life is like riding a bicycle. To keep your balance you must keep moving. A.E.
Guru

Join Date: Dec 2008
Location: Long Island NY
Posts: 12262
#14

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/01/2017 9:20 PM

That's what I get, too.

__________________
"Don't disturb my circles." translation of Archimedes last words
Guru

Join Date: Apr 2010
Location: Trantor
Posts: 5223
#2

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

02/28/2017 8:52 PM

I'm guessing it's the answer to Life, the Universe, and Everything: 42.

If I understand the challenge correctly, the 42nd prime is 181. So what number can be partitioned exactly 181 ways? I'm guessing it's 42.

When n is the number 4, p(n) = 5 ways. When n is 8, p(n) is 22. Doing a simplistic extrapolation (a massive assumption) to p(n) =181, the number n is going to be somewhere in the 40s. So it makes sense to guess 42.

__________________
Whiskey, women -- and astrophysics. Because sometimes a problem can't be solved with just whiskey and women.
Guru

Join Date: Mar 2007
Location: at the beach in Florida
Posts: 19472
#6

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

02/28/2017 11:24 PM

No it would be much lower than that, remember the addends can be used in different order.....15 would be 176 partitions if the numbers were used in only one order....if you start allowing different orders to be counted, then the number goes lower...it's probably like 10...which by the way is 42....or even lower into the single digits....

__________________
Life is like riding a bicycle. To keep your balance you must keep moving. A.E.
Guru

Join Date: Dec 2016
Posts: 2914
#7

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

02/28/2017 11:50 PM

As I understand it, the question is not speaking of the 42nd prime number, but is asking for the value of n for which p(n) is prime and the 42nd largest prime p(n) in the sequence of prime p(n)s.

If this is the case, then the previous 41 n's for which p(n) is prime are: 2, 3, 4, 5, 6, 13, 36, 77, 132, 157, 168, 186, 188, 212, 216, 302, 366, 417, 440, 491, 498, 525, 546, 658, 735, 753, 825, 841, 863, 1085, 1086, 1296, 1477, 1578, 1586, 1621, 1793, 2051, 2136, 2493, 2502; the 42nd in this sequence being 2508.

Listing the first few n's in this sequence, and looking at the number of partitions for each to see if they are prime, we see

o, n, p(n) (ordinal, n, #partitions)

1st, 2, 2

2nd, 3, 3

3rd, 4, 5

4th, 5, 7

5th, 6, 11

6th, 13, 101

7th, 36, 17 977

8th, 77, 10 619 863

9th, 132, 6 620 830 889

10th, 157, 80 630 964 769

...

41st, 2502, 3 019 564 607 799 532 159 016 586 951 616 642 980 389 816 614 848 623

42nd, 2508, 3 513 035 269 942 590 955 686 749 126 214 187 667 970 579 050 845 937

All 42 p(n)s are prime numbers whilst all the p(n)s between them are composite. The answer is therefore n = 2508, if I understand the question correctly.

Guru

Join Date: Aug 2005
Posts: 4182
#16

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/02/2017 6:58 AM

That's what I got from

http://www.numericana.com/data/partition.htm

A page which seems to have been designed to solve this problem!

__________________
We are alone in the universe, or, we are not. Either way it's incredible... Adapted from R. Buckminster Fuller/Arthur C. Clarke
Guru

Join Date: Dec 2016
Posts: 2914
#18

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/02/2017 11:24 AM

... or the page from which the OP chose the problem! (inspired by reading Hitchhiker's Guide.. no doubt)

Guru

Join Date: Apr 2009
Location: Tampa, Florida, USA
Posts: 2053
#11

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/01/2017 10:32 AM

I'm puzzled, not only by the OP puzzle, but by your statement that there are 5 ways to get a value of 4 by adding positive integers. I can only come up with 4 unique ways:

1+3 = 4

1+1+2 = 4

1+1+1+1 = 4

2+2 = 4

What's the 5th?

Also, I only come have been able to come up with 21 unique ways to get positive integers to add to 8. I won't list them here...but if I've missed one way to get a value of 4, then that might add one more way to get to a value of 8.

__________________
J B
Guru

Join Date: Mar 2007
Location: at the beach in Florida
Posts: 19472
#12

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/01/2017 11:45 AM

The 5th is 4....

__________________
Life is like riding a bicycle. To keep your balance you must keep moving. A.E.
Guru

Join Date: Mar 2009
Posts: 507
#25

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/07/2017 11:57 AM

and the sixth is 5-1?

Guru

Join Date: Dec 2016
Posts: 2914
#13

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/01/2017 1:33 PM

The number n is itself considered a partition in spite of how partitions are commonly defined, both the OP's definition and what is often seen in the literature. Looking at the OP's definition,

"If p(n) is the number of partitions of n, defined as the number of ways to write the integer n as a sum of positive integers ...," two problems immediately arise:

n, by itself, is (1) not a sum. "Oh, but we can add zero to it to make it one!" - except that (2) zero is not a positive integer. 'Positive' and 'negative' are defined in terms of zero, and so to include zero in either set would result in a circular definition.

Your confusion is understandable but, yes, n is considered a partition of itself (the actual definition of what constitutes a partition is much more rigorous) and so, in the case of 4, we have 5 partitions:

4

3 + 1

2 + 2

2 + 1 + 1

1 + 1 + 1 + 1

Guru

Join Date: Apr 2009
Location: Tampa, Florida, USA
Posts: 2053
#15

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/02/2017 6:50 AM

You've perfectly explained my rationale for not considering 4 as a partition of 4 (based on the OP's definition and the fact that 0 is not a positive or negative integer).

However, if n is still considered an partition of n, then so be it.

__________________
J B
Guru

Join Date: Dec 2016
Posts: 2914
#19

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/02/2017 11:40 AM

The rationale for including n as its own partition derives from set theory, but one wouldn't know this from the way the definition is commonly described (as we see in the OP and in many other places).

Guru

Join Date: Dec 2016
Posts: 2914
#20

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/02/2017 12:42 PM

There is another, more subtle, reason for disallowing addition of zero (besides its not being a positive integer): If you could add one zero, you could add as many as you like, up to infinitely many of them without changing the sum, resulting in an infinite number of 'degenerate' unique partitions for every n:

n

n + 0

n + 0 + 0

...

Guru

Join Date: Dec 2008
Location: Long Island NY
Posts: 12262
#21

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/02/2017 1:25 PM

However, often a set theory mathematician wants infinity to be the answer.

__________________
"Don't disturb my circles." translation of Archimedes last words
Off Topic (Score 5)
Guru

Join Date: Dec 2016
Posts: 2914
#22

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/02/2017 1:43 PM

Degenerates, all.

Off Topic (Score 5)
Guru

Join Date: Apr 2009
Location: Tampa, Florida, USA
Posts: 2053
#23

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/02/2017 3:10 PM

If you could add one zero, you could add as many as you like, up to infinitely many of them without changing the sum, resulting in an infinite number of 'degenerate' unique partitions for every n

Which is one of the prime reasons it makes sense that n should not be a partition of itself in the context of how this problem has been defined.

__________________
J B
Guru

Join Date: Dec 2016
Posts: 2914
#24

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/02/2017 3:16 PM

The definition, as posted, is of course incomplete.

2
Guru

Join Date: Dec 2016
Posts: 2914
#5

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

02/28/2017 11:09 PM

I'm guessing n = 2508.

p(2508) = , which is prime

Guru

Join Date: Mar 2007
Location: at the beach in Florida
Posts: 19472
#8

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/01/2017 2:09 AM

By Jove, I think you're right.....

__________________
Life is like riding a bicycle. To keep your balance you must keep moving. A.E.
Guru

Join Date: Dec 2016
Posts: 2914
#10

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/01/2017 10:09 AM

It's weird, but yesterday evening I'd written the last line in #5 as:

p(2508) = 3 513 035 269 942 590 955 686 749 126 214 187 667 970 579 050 845 937, which is prime

p(2508) = , which is prime

???

The Architect

Join Date: Dec 2004
Location: GlobalSpec, Troy NY
Posts: 395
#26

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/20/2017 4:44 PM

I was wondering that too... turns out the original post included an external image (on wolframalpha.com), and that image is no longer available (so it was hidden)

__________________
Mark Gaulin
Guru

Join Date: Dec 2016
Posts: 2914
#27

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

04/06/2017 1:28 AM

That must've been it. The image appeared for a while, but then disappeared. I guess the image was created dynamically and then the storage for it on wolfram's site reclaimed, resulting in a dead link?

You're CR4 member #1! When I hover the mouse over your name, at the bottom it reads cr4.globalspec.com/member/1/mgaulin. As The Architect (love The Matrix reference) you designed CR4's website then? Nice job.

Guru

Join Date: Apr 2010
Location: Trantor
Posts: 5223
#9

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/01/2017 7:08 AM

I have since plotted more points, and I now think the answer is 19. Here's my new graph. The intersection of the blue line at 181 with the black line that plots p(n) vs n, occurs between 18 and 19, but if my curve had a finer set of points, it looks like it would intersect at 19.

Perhaps AW is correct in thinking that the questions asks for the 42nd prime p(n). If so, GA to his answer.

(Though I still like my original guess of 42. I mean, come on... who doesn't like a good Hitchhiker's Guide to the Galaxy reference?)

__________________
Whiskey, women -- and astrophysics. Because sometimes a problem can't be solved with just whiskey and women.
Guru

Join Date: Aug 2005
Posts: 4182
#17

### Re: Puzzling Prime Partition: Newsletter Challenge (March 2017)

03/02/2017 7:10 AM

Unfortunately 181 lies between p(15) and p(16)

__________________
We are alone in the universe, or, we are not. Either way it's incredible... Adapted from R. Buckminster Fuller/Arthur C. Clarke
Interested in this topic? By joining CR4 you can "subscribe" to