Author |
Topic: A rather unusual sequence (Read 3602 times) |
|
Deedlit
Senior Riddler
Posts: 476
|
 |
A rather unusual sequence
« on: Apr 2nd, 2005, 3:16am » |
 Quote  Modify
|
Call a set S of natural numbers n-primitive if, for any k in S larger than n,
1. k is not the multiple on any other element of S.
2. k divides the product of all smaller elements in S.
Let a_n be the largest possible member of an n-primitive set. What are a_1 through a_14?
|
| « Last Edit: Apr 5th, 2005, 9:29am by Deedlit » |
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
|
Re: A rather unusual sequence
« Reply #1 on: Apr 2nd, 2005, 11:45pm » |
Quote Modify
|
Just for clarification: how do you classify the set S = {6, 10, 15} ?
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: A rather unusual sequence
« Reply #2 on: Apr 3rd, 2005, 12:25am » |
Quote Modify
|
That's n-primitive for n >= 10.
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: A rather unusual sequence
« Reply #3 on: Apr 3rd, 2005, 1:51am » |
Quote Modify
|
I'm probably missing something here, but...
Should 2. be "k divides the product of all elements equal to or less"? Otherwise, in Barukh's example, 10 doesn't divide 6. If we stick to 2. as it is given, then should it not be only for k=15?
However, under the modified version, could we not simply have S = {k}? k is not a multiple of any other element (there are none), and it divides the product of elements equal to or less (itself).
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A rather unusual sequence
« Reply #4 on: Apr 3rd, 2005, 3:47am » |
Quote Modify
|
If Sir Col is right (and I think he is):
on Apr 3rd, 2005, 12:25am, Deedlit wrote:| That's n-primitive for n >= 10. |
|
...this should read n > 10, and this shows that a11 >= 15.
OK?
|
| « Last Edit: Apr 4th, 2005, 12:22am by Barukh » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: A rather unusual sequence
« Reply #5 on: Apr 3rd, 2005, 7:12am » |
Quote Modify
|
Well, if n = 10, then the rule applies only to 15, which satisfies both rules. So I think what I wrote is correct.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A rather unusual sequence
« Reply #6 on: Apr 4th, 2005, 12:26am » |
Quote Modify
|
Aha! Here's what I got:
I don't know how to define a1 through a8.
a9 = 12
a10 = a11 = 15
a12 = a13 = 45
a14 = 315
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: A rather unusual sequence
« Reply #7 on: Apr 4th, 2005, 5:52am » |
Quote Modify
|
ai = i for i <= 8, vacuously. Your a9 through a11 are correct, but not the higher ones.
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: A rather unusual sequence
« Reply #8 on: Apr 4th, 2005, 11:07am » |
Quote Modify
|
Apologies, but there's no eurhka with me yet; I'm just not getting the definition/notation:
If S = {6, 10, 15}, are we saying that S is 10-primitive, because for each element in S that is larger than 10 (only 15 in this case) it is neither a multiple of 6 nor 10, and 15 also divides 6*10=60? Hence a10 = 15.
For that same reasons are we also saying that S is 11-primitive? And so, a11 = 15.
In the same way, could we not say that S is 12-, 13-, and 14- primitive?
Also I don't quite understand how a1 = 1 (and similarly through to a8), as this would suggest that S = {1}, and this is not primitive for any n.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A rather unusual sequence
« Reply #9 on: Apr 4th, 2005, 11:57am » |
Quote Modify
|
on Apr 4th, 2005, 11:07am, Sir Col wrote:| In the same way, could we not say that S is 12-, 13-, and 14- primitive? |
|
IMHO, we can.
Deedlit, I don't see how my solution may be improved e.g. for a12? Or, may be, I misinterpret the question? Then: what is S = {6, 10, 12, 45}?
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: A rather unusual sequence
« Reply #10 on: Apr 4th, 2005, 4:58pm » |
Quote Modify
|
I forgot to ask before, if ai = i for i <= 8, then why does it not hold for i > 8 ? Or are we saying that ai is undefined for i <= 8, because there are no 1-, 2-, ... , 8-primitive sets, and S = {8,9,12}, being 9-primitive, is the first valid set?
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: A rather unusual sequence
« Reply #11 on: Apr 4th, 2005, 10:26pm » |
Quote Modify
|
on Apr 4th, 2005, 11:07am, Sir Col wrote:Apologies, but there's no eurhka with me yet; I'm just not getting the definition/notation:
If S = {6, 10, 15}, are we saying that S is 10-primitive, because for each element in S that is larger than 10 (only 15 in this case) it is neither a multiple of 6 nor 10, and 15 also divides 6*10=60? Hence a10 = 15.
|
|
Yes, except it only shows that a10 >= 15; there could be another S with a higher value.
Quote:| For that same reasons are we also saying that S is 11-primitive? And so, a11 = 15. |
|
Again, a11 >= 15.
Quote:| In the same way, could we not say that S is 12-, 13-, and 14- primitive? |
|
Indeed.
Quote:| Also I don't quite understand how a1 = 1 (and similarly through to a8), as this would suggest that S = {1}, and this is not primitive for any n. |
|
Technically, it is; a "for all" statement is considered to be true when there are no elements satisfying the requirements.
Quote:| Deedlit, I don't see how my solution may be improved e.g. for a12? Or, may be, I misinterpret the question? |
|
It looks like you are allowing only one element to be greater than n; you are allowed to have more!
Quote:| I forgot to ask before, if ai = i for i <= 8, then why does it not hold for i > 8 ? Or are we saying that ai is undefined for i <= 8, because there are no 1-, 2-, ... , 8-primitive sets, and S = {8,9,12}, being 9-primitive, is the first valid set? |
|
Well, that's what needs to be analyzed, but your own example shows that a9 > 9. We aren't saying that the ai are undefined, just that, for example, a 6-primitive set doesn't contain any elements larger than 6.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A rather unusual sequence
« Reply #12 on: Apr 5th, 2005, 2:13am » |
Quote Modify
|
How about this?
| hidden: | a12 = a13 = 75, a14 = 3675.
Explanations for a12 are given in the following table.
2 3 5
-----------
6 = 1 1
10 = 1 1
12 = 2 1
45 = 2 1
75 = 1 2
|
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A rather unusual sequence
« Reply #13 on: Apr 5th, 2005, 2:30am » |
Quote Modify
|
How would you classify a set like {0, 163567278} ? 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: A rather unusual sequence
« Reply #14 on: Apr 5th, 2005, 9:28am » |
Quote Modify
|
on Apr 5th, 2005, 2:30am, towr wrote:| How would you classify a set like {0, 163567278} ? |
|
Errr, right. The numbers have to be natural numbers. (edited original post)
|
| « Last Edit: Apr 5th, 2005, 9:29am by Deedlit » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: A rather unusual sequence
« Reply #15 on: Apr 5th, 2005, 9:31am » |
Quote Modify
|
on Apr 5th, 2005, 2:13am, Barukh wrote:How about this?
| hidden: | a12 = a13 = 75, a14 = 3675.
Explanations for a12 are given in the following table.
2 3 5
-----------
6 = 1 1
10 = 1 1
12 = 2 1
45 = 2 1
75 = 1 2
|
|
|
Closer, but not quite! Well not so close for a14.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A rather unusual sequence
« Reply #16 on: Apr 6th, 2005, 7:55am » |
Quote Modify
|
Another clarification: do the elements of S have to be unique?
Otherwise wouldn't, for instance, any set of the form { 4, 4, ..., 4, 22n-1 } with n fours be 4-primitive? (Which would then show that there's no largest-possible member of a (4-or-greater)-primitive set since n could be chosen arbitrarily large, right?)
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A rather unusual sequence
« Reply #17 on: Apr 6th, 2005, 8:49am » |
Quote Modify
|
on Apr 6th, 2005, 7:55am, SMQ wrote:| Otherwise wouldn't, for instance, any set of the form { 4, 4, ..., 4, 22n-1 } with n fours be 4-primitive? (Which would then show that there's no largest-possible member of a (4-or-greater)-primitive set since n could be chosen arbitrarily large, right?)--SMQ |
|
This won't work for the simple reason: 4 clearly divides 22n-1, and therefore violates the first condition. So, the set is not 4-primitive.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A rather unusual sequence
« Reply #18 on: Apr 6th, 2005, 9:01am » |
Quote Modify
|
Quote:
Erm, no, it doesn't... 4 divides 22n, but not 22n-1.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A rather unusual sequence
« Reply #19 on: Apr 6th, 2005, 9:27am » |
Quote Modify
|
on Apr 6th, 2005, 9:01am, SMQ wrote:
Erm, no, it doesn't... 4 divides 22n, but not 22n-1.
--SMQ |
|
22n-1 = 4*22n-3.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A rather unusual sequence
« Reply #20 on: Apr 6th, 2005, 9:53am » |
Quote Modify
|
   hookay, um, don't mind me, I'm new here 
OK, back to the uniqueness thing, though, how about a set of the form {6, 6, ..., 6, 3n} with n sixes? That's 6-primitive, and n can be arbitrarily large, right?
So without uniqueness there is no largest possible member of an n-primitive set with n >= 6, and therefore we still need to stipulate uniqueness, yes?
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A rather unusual sequence
« Reply #21 on: Apr 6th, 2005, 10:00am » |
Quote Modify
|
On a different track, I think I've found a10 = a11 = 25, where S = {6, 10, 15, 25} or {9, 10, 15, 25} by exhaustive search assuming elements of S have to be unique.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A rather unusual sequence
« Reply #22 on: Apr 6th, 2005, 10:47am » |
Quote Modify
|
on Apr 6th, 2005, 10:00am, SMQ wrote:On a different track, I think I've found a10 = a11 = 25, where S = {6, 10, 15, 25} or {9, 10, 15, 25} by exhaustive search assuming elements of S have to be unique.
--SMQ |
|
Nicely done, SMQ! So, my results were wrong even for these numbers.
As for the higher elements, I believe the following is the best:
| hidden: |
a12 = a13 = 625:
2 3 5
-------
1 1
1 1
2 1
2 1
1 2
5
4
a14 = 2 251 875 390 625:
2 3 5 7
---------
1 1
1 1
2 1
1 1
2 1 1
1 2 2
5 4
10 4
8 8
|
Did I miss something yet again?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A rather unusual sequence
« Reply #23 on: Apr 6th, 2005, 11:36am » |
Quote Modify
|
Um, is there a reason your table for a14 didn't end:
| hidden: |
2 3 5 7
-----------
...
0 0 0 16 |
giving a[14] = 716 = 33 232 930 569 601?
--SMQ
|
| « Last Edit: Apr 6th, 2005, 11:38am by SMQ » |
IP Logged |
--SMQ
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: A rather unusual sequence
« Reply #24 on: Apr 6th, 2005, 11:47am » |
Quote Modify
|
As far as the question of repeated elements is concerned, this is clearly disallowed by the hypothesis that S be a set of natural numbers.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print