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


Challenge Questions Blog

Challenge Questions

Stop in and exercise your brain. Talk about this month's Challenge from Specs & Techs or similar puzzles.

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
Close
Close
Close
27 comments

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.

Reply

Interested in this topic? By joining CR4 you can "subscribe" to
this discussion and receive notification when new comments are added.

Comments rated to be Good Answers:

These comments received enough positive ratings to make them "good answers".

Comments rated to be "almost" Good Answers:

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: 17378
Good Answers: 995
#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.
Reply
Guru

Join Date: Dec 2016
Posts: 2706
Good Answers: 97
#3
In reply to #1

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.

Reply
Guru

Join Date: Mar 2007
Location: at the beach in Florida
Posts: 17378
Good Answers: 995
#4
In reply to #3

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.
Reply Score 1 for Good Answer
Guru
Engineering Fields - Electrical Engineering - Been there, done that, still doing it. Engineering Fields - Control Engineering - New Member

Join Date: Dec 2008
Location: Long Island NY
Posts: 11831
Good Answers: 741
#14
In reply to #4

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
Reply
Guru
Engineering Fields - Optical Engineering - Member Engineering Fields - Engineering Physics - Member Engineering Fields - Systems Engineering - Member

Join Date: Apr 2010
Location: Trantor
Posts: 5056
Good Answers: 604
#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.
Reply
Guru

Join Date: Mar 2007
Location: at the beach in Florida
Posts: 17378
Good Answers: 995
#6
In reply to #2

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.
Reply
Guru

Join Date: Dec 2016
Posts: 2706
Good Answers: 97
#7
In reply to #2

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.

Reply Score 1 for Good Answer
Guru

Join Date: Aug 2005
Location: Hemel Hempstead, UK
Posts: 3971
Good Answers: 218
#16
In reply to #7

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
Reply Score 1 for Good Answer
Guru

Join Date: Dec 2016
Posts: 2706
Good Answers: 97
#18
In reply to #16

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)

Reply
Guru
Engineering Fields - Control Engineering - Time to take control United States - Member - New Member Engineering Fields - Systems Engineering - New Member Engineering Fields - Mechanical Engineering - New Member

Join Date: Apr 2009
Location: Tampa, Florida, USA
Posts: 1993
Good Answers: 80
#11
In reply to #2

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
Reply
Guru

Join Date: Mar 2007
Location: at the beach in Florida
Posts: 17378
Good Answers: 995
#12
In reply to #11

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.
Reply
Guru

Join Date: Mar 2009
Posts: 507
#25
In reply to #12

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

03/07/2017 11:57 AM

and the sixth is 5-1?

Reply
Guru

Join Date: Dec 2016
Posts: 2706
Good Answers: 97
#13
In reply to #11

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

Reply
Guru
Engineering Fields - Control Engineering - Time to take control United States - Member - New Member Engineering Fields - Systems Engineering - New Member Engineering Fields - Mechanical Engineering - New Member

Join Date: Apr 2009
Location: Tampa, Florida, USA
Posts: 1993
Good Answers: 80
#15
In reply to #13

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
Reply
Guru

Join Date: Dec 2016
Posts: 2706
Good Answers: 97
#19
In reply to #15

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).

Reply
Guru

Join Date: Dec 2016
Posts: 2706
Good Answers: 97
#20
In reply to #15

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

...

Reply
Guru
Engineering Fields - Electrical Engineering - Been there, done that, still doing it. Engineering Fields - Control Engineering - New Member

Join Date: Dec 2008
Location: Long Island NY
Posts: 11831
Good Answers: 741
#21
In reply to #20

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
Reply Off Topic (Score 5)
Guru

Join Date: Dec 2016
Posts: 2706
Good Answers: 97
#22
In reply to #21

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

03/02/2017 1:43 PM

Degenerates, all.

Reply Off Topic (Score 5)
Guru
Engineering Fields - Control Engineering - Time to take control United States - Member - New Member Engineering Fields - Systems Engineering - New Member Engineering Fields - Mechanical Engineering - New Member

Join Date: Apr 2009
Location: Tampa, Florida, USA
Posts: 1993
Good Answers: 80
#23
In reply to #20

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
Reply
Guru

Join Date: Dec 2016
Posts: 2706
Good Answers: 97
#24
In reply to #23

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

03/02/2017 3:16 PM

The definition, as posted, is of course incomplete.

Reply
2
Guru

Join Date: Dec 2016
Posts: 2706
Good Answers: 97
#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

Reply Good Answer (Score 2)
Guru

Join Date: Mar 2007
Location: at the beach in Florida
Posts: 17378
Good Answers: 995
#8
In reply to #5

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.
Reply
Guru

Join Date: Dec 2016
Posts: 2706
Good Answers: 97
#10
In reply to #8

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

but today it simply reads:

p(2508) = , which is prime

???

Reply
The Architect
Engineering Fields - Software Engineering - S/W Architect Popular Science - Evolution - Fascinating! Fans of Old Computers - TRS-80 - A fine computer United States - US - Statue of Liberty - NY

Join Date: Dec 2004
Location: GlobalSpec, Troy NY
Posts: 395
Good Answers: 5
#26
In reply to #10

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)

Reply
Guru

Join Date: Dec 2016
Posts: 2706
Good Answers: 97
#27
In reply to #26

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.

Reply
Guru
Engineering Fields - Optical Engineering - Member Engineering Fields - Engineering Physics - Member Engineering Fields - Systems Engineering - Member

Join Date: Apr 2010
Location: Trantor
Posts: 5056
Good Answers: 604
#9

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

03/01/2017 7:08 AM

I'm revising my answer.

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.
Reply
Guru

Join Date: Aug 2005
Location: Hemel Hempstead, UK
Posts: 3971
Good Answers: 218
#17
In reply to #9

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
Reply
Reply to Blog Entry 27 comments
Interested in this topic? By joining CR4 you can "subscribe" to
this discussion and receive notification when new comments are added.

Comments rated to be Good Answers:

These comments received enough positive ratings to make them "good answers".

Comments rated to be "almost" Good Answers:

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

Users who posted comments:

Andrew Westman (11); JBTardis (3); mgaulin (1); Randall (2); redfred (2); SolarEagle (5); Usbport (2); WilhelmHKoen (1)

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

Advertisement