wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> A rather unusual sequence
        
(Message started by: Deedlit on Apr 2^nd, 2005, 3:16am)

Title: A rather unusual sequence
Post by Deedlit on Apr 2^nd, 2005, 3:16am

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?

Title: Re: A rather unusual sequence
Post by Barukh on Apr 2^nd, 2005, 11:45pm

Just for clarification: how do you classify the set S = {6, 10, 15} ?

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 3^rd, 2005, 12:25am

That's n-primitive for n >= 10.

Title: Re: A rather unusual sequence
Post by Sir Col on Apr 3^rd, 2005, 1:51am

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

Title: Re: A rather unusual sequence
Post by Barukh on Apr 3^rd, 2005, 3:47am

If Sir Col is right ~~(and I think he is):~~

on 04/03/05 at 00:25:48, Deedlit wrote:

That's n-primitive for n >= 10.

~~...this should read n > 10, and this shows that a₁₁ >= 15.~~

OK?

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 3^rd, 2005, 7:12am

Well, if n = 10, then the rule applies only to 15, which satisfies both rules. So I think what I wrote is correct.

Title: Re: A rather unusual sequence
Post by Barukh on Apr 4^th, 2005, 12:26am

Aha! Here's what I got:

[hide]I don't know how to define a₁ through a₈.

a₉ = 12
a₁₀ = a₁₁ = 15
a₁₂ = a₁₃ = 45
a₁₄ = 315
[/hide]

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 4^th, 2005, 5:52am

[hide]a_i = i for i <= 8, vacuously. Your a₉ through a₁₁ are correct, but not the higher ones.[/hide]

Title: Re: A rather unusual sequence
Post by Sir Col on Apr 4^th, 2005, 11:07am

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 a₁₀ = 15.

For that same reasons are we also saying that S is 11-primitive? And so, a₁₁ = 15.

In the same way, could we not say that S is 12-, 13-, and 14- primitive?

Also I don't quite understand how a₁ = 1 (and similarly through to a₈), as this would suggest that S = {1}, and this is not primitive for any n.

Title: Re: A rather unusual sequence
Post by Barukh on Apr 4^th, 2005, 11:57am

on 04/04/05 at 11:07:09, 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 a₁₂? Or, may be, I misinterpret the question? Then: [hide]what is S = {6, 10, 12, 45}?[/hide]

Title: Re: A rather unusual sequence
Post by Sir Col on Apr 4^th, 2005, 4:58pm

I forgot to ask before, if a_i = i for i <= 8, then why does it not hold for i > 8 ? Or are we saying that a_i 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?

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 4^th, 2005, 10:26pm

on 04/04/05 at 11:07:09, Sir Col wrote:

Yes, except it only shows that a₁₀ >= 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, a₁₁ = 15.

Again, a₁₁ >= 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 a₁ = 1 (and similarly through to a₈), 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 a₁₂? 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 a₉ > 9. We aren't saying that the a_i are undefined, just that, for example, a 6-primitive set doesn't contain any elements larger than 6.

Title: Re: A rather unusual sequence
Post by Barukh on Apr 5^th, 2005, 2:13am

How about this?

[hideb] a₁₂ = a₁₃ = 75, a₁₄ = 3675.

Explanations for a₁₂ are given in the following table.

2 3 5
-----------
6 = 1 1
10 = 1 1
12 = 2 1
45 = 2 1
75 = 1 2
[/hideb]

Title: Re: A rather unusual sequence
Post by towr on Apr 5^th, 2005, 2:30am

How would you classify a set like {0, 163567278} ? :P

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 5^th, 2005, 9:28am

on 04/05/05 at 02:30:03, towr wrote:

How would you classify a set like {0, 163567278} ? :P

Errr, right. :P The numbers have to be natural numbers. (edited original post)

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 5^th, 2005, 9:31am

on 04/05/05 at 02:13:06, Barukh wrote:

How about this?

[hideb] a₁₂ = a₁₃ = 75, a₁₄ = 3675.

Explanations for a₁₂ are given in the following table.

2 3 5
-----------
6 = 1 1
10 = 1 1
12 = 2 1
45 = 2 1
75 = 1 2
[/hideb]

Closer, but not quite! Well not so close for a₁₄. :P

Title: Re: A rather unusual sequence
Post by SMQ on Apr 6^th, 2005, 7:55am

Another clarification: do the elements of S have to be unique?

Otherwise wouldn't, for instance, any set of the form { 4, 4, ..., 4, 2^2n-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

Title: Re: A rather unusual sequence
Post by Barukh on Apr 6^th, 2005, 8:49am

on 04/06/05 at 07:55:25, SMQ wrote:

Otherwise wouldn't, for instance, any set of the form { 4, 4, ..., 4, 2^2n-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 2^2n-1, and therefore violates the first condition. So, the set is not 4-primitive.

Title: Re: A rather unusual sequence
Post by SMQ on Apr 6^th, 2005, 9:01am

Quote:

4 clearly divides 2^2n-1

Erm, no, it doesn't... 4 divides 2²ⁿ, but not 2^2n-1.

--SMQ

Title: Re: A rather unusual sequence
Post by towr on Apr 6^th, 2005, 9:27am

on 04/06/05 at 09:01:03, SMQ wrote:

Erm, no, it doesn't... 4 divides 2²ⁿ, but not 2^2n-1.

--SMQ

2^2n-1 = 4*2^2n-3.
::)

Title: Re: A rather unusual sequence
Post by SMQ on Apr 6^th, 2005, 9:53am

:o :-[ :'( hookay, um, don't mind me, I'm new here :D

OK, back to the uniqueness thing, though, how about a set of the form {6, 6, ..., 6, 3ⁿ} 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

Title: Re: A rather unusual sequence
Post by SMQ on Apr 6^th, 2005, 10:00am

On a different track, I think I've found a₁₀ = a₁₁ = [hide]25, where S = {6, 10, 15, 25} or {9, 10, 15, 25}[/hide] by exhaustive search assuming elements of S have to be unique.

--SMQ

Title: Re: A rather unusual sequence
Post by Barukh on Apr 6^th, 2005, 10:47am

on 04/06/05 at 10:00:51, SMQ wrote:

On a different track, I think I've found a₁₀ = a₁₁ = [hide]25, where S = {6, 10, 15, 25} or {9, 10, 15, 25}[/hide] 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:

[hideb]
a₁₂ = a₁₃ = 625:

2 3 5
-------
1 1
1 1
2 1
2 1
1 2
5
4

a₁₄ = 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

[/hideb]
Did I miss something yet again? ::)

Title: Re: A rather unusual sequence
Post by SMQ on Apr 6^th, 2005, 11:36am

Um, is there a reason your table for a₁₄ didn't end:
[hideb]
2 3 5 7 ----------- ... 0 0 0 16[/hideb]
giving a_[14] = [hide]7¹⁶ = 33 232 930 569 601[/hide]?

--SMQ

Title: Re: A rather unusual sequence
Post by Obob on Apr 6^th, 2005, 11:47am

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.

Title: Re: A rather unusual sequence
Post by Sir Col on Apr 6^th, 2005, 2:48pm

on 04/05/05 at 09:28:20, Deedlit wrote:

Errr, right. :P The numbers have to be natural numbers. (edited original post)

I'm surprised that towr has remained silent on this: N = {0,1,2,...} or N = {1,2,3,...}? ;)

http://en.wikipedia.org/wiki/Natural_number

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 6^th, 2005, 5:28pm

Wow, a lot of activity all of a sudden!

Quote:

I'm surprised that towr has remained silent on this: N = {0,1,2,...} or N = {1,2,3,...}?

LOL... okay, positive integers then.

Quote:

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?

As Obob said, a set is defined only by which elements it contains - no multiple elements.

Quote:

a10 = a11 = [hide]25, where S = {6, 10, 15, 25} or {9, 10, 15, 25}[/hide]

Y'know, I knew that was the answer, but I still said Barukh was right. :-[

There's still work to be done on a₁₄, though. ;D

Title: Re: A rather unusual sequence
Post by towr on Apr 7^th, 2005, 3:57am

on 04/06/05 at 14:48:18, Sir Col wrote:

I'm surprised that towr has remained silent on this: N = {0,1,2,...} or N = {1,2,3,...}? ;)

http://en.wikipedia.org/wiki/Natural_number

I had thought about mentioning it. But then I thought let's give 'm a break. We all know what he means anyway.

Title: Re: A rather unusual sequence
Post by SMQ on Apr 7^th, 2005, 5:03am

How about this for a₁₄:
[hideb]2 3 5 7 ------------ 1 1 . . 1 . 1 . 1 . . 1 . 1 1 1 . 2 . 2 . 4 . 1 . 8 2 . . 7 4 . . 6 8 . . 5 16 . . 4 32 . . 3 64 . . 2 128 . . 1 256 . . . 512 5 . . 511 10 ... . . 1 5*2^511 . . . 5*2^512
a₁₄ = 7^{5*2^512}
[/hideb]

My exhaustive solver ran out of memory trying to calculate that (is there an efficient way to determine whether a < b from their prime factorizations alone?), but I spotted the pattern...I think. ;D

--SMQ

Title: Re: A rather unusual sequence
Post by SMQ on Apr 7^th, 2005, 6:32am

Whoops, I can do better than that yet:
[hideb]
2 3 5 7 ---------------- 1 . 1 . 2 1 . . 1 . . 1 1 2 . . . 3 1 1 . 6 . 2 . 12 . 1 . 24 2 . . 23 4 . ... . 1 2^24 . . . 2^25 5 ... . . 1 5*2^(2^25 - 1) . . . 5*2^2^25
a₁₄ = a₁₅ = a₁₆ = a₁₇ = a₁₈ = a₁₉ = 7^(5*2^2^25)
or about 10^10^10^10.
[/hideb]

--SMQ

Title: Re: A rather unusual sequence
Post by SMQ on Apr 7^th, 2005, 8:11am

Continuing the pattern, I get:
[hideb]
a_i = i for 1 <= i <= 8
a₉ = 12
a₁₀ = a₁₁ = 25
a₁₂ = a₁₃ = 625
a_j = 7^(5*2^2^25) for 14 <= j <= 19
a₂₀ = a₂₁ = 7^(5*2^(3*2^25))
2^^11 < a₂₂ = a₂₃ < a₂₄ = a₂₅ < 2^^12
[/hideb]

where ^^ represents repeated exponentiation (e.g. 2^^3 = 2^2^2 = 16)

--SMQ
(edited for typo, increased clarity)

Title: Re: A rather unusual sequence
Post by Barukh on Apr 7^th, 2005, 8:15am

Unbelievable! Congratulations, SMQ! I came to the same algorithm too late.

But let's wait till Deedlit's judgement ;D

on 04/07/05 at 05:03:25, SMQ wrote:

How about this for a₁₄My exhaustive solver ran out of memory trying to calculate that (is there an efficient way to determine whether a < b from their prime factorizations alone?)

Yes: simply compare their logarithms (which were invented exactly for that purpose).

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 7^th, 2005, 1:46pm

Well done, SMQ and Barukh! :D You've found the basic pattern. Unfortunately, SMQ's second entry doesn't work... there aren't enough factors to get 18.

There are still some improvements to be made - one thing you guys missed will bump the number by a LOT, plus a few details that will make lesser improvements.

Quote:

2^^11 < a22 = a23 < a24 = a25 < 2^^12

Are you sure about that? ;D

Title: Re: A rather unusual sequence
Post by SMQ on Apr 7^th, 2005, 1:56pm

Quote:

there aren't enough factors to get 18.

See, that's what I get for doing it by hand--the balance between hand solving and machine solving on this one, for me at least, is a bit, ah, delicate... The computer really isn't happy thinking about numbers this big, even in prime factor form, and my hand-solving skills are a bit ~~sloppy~~ rusty ;)

Quote:

Are you sure about that? ;D

Hmm, I actually meant to write 11^{2^^11} < ... < 11^{2^^12}, but even then, In light of this post, and the record so far, no, I'm not sure about it at all. ;D

--SMQ

Title: Re: A rather unusual sequence
Post by Barukh on Apr 8^th, 2005, 4:51am

It seems there are just three members discussing this problem, and the answers may seem rather cryptic for the others. So, I think explaining an approach to the solution may be of some benefit.

I will consider the case n=14, since it is by any means the most challenging. To construct the set S, divide all its elements into 2 groups: those less or equal 14 (S₁); and all the rest (S₂).

The elements from the first group may be considered as “building blocks”. Formally, there are no restrictions on them, but actually primes and prime factors greatly restrict the size of the elements in S₂, so I have excluded them. The remaining candidates for S₁ are: 6, 10, 12, 14. Let’s summarize their factorization in the following table:

2 3 5 7
---------------------------
6 1 1
10 1 1
12 2 1
14 1 1

This shows that any element from S₂ can have only prime factors 2, 3, 5, 7. The general strategy to construct larger and larger elements in S₂ is as follows:

1. Begin with as many distinct prime factors as possible, with as big powers as possible.

2. Try to reduce the power of any prime factor by one and double the powers of all the other factors. Repeat this until the power of the chosen prime factor is more than 1.

3. Reduce the number of prime factors and repeat.

It is quite clear that no element in S₂ may have all four factors. Also, any combination with three factors including a 2 is also impossible (why?). So, the best I can start with is the following (I give only the factorizations):

3 5 7
-------------------
2 1 1
1 2 2

Next, I reduce the number of factors to two. Here, I have several choices and I am not sure what is the best (probably, SMQ had in mind this part that was programmed). I proceed with (3, 7):

3 5 7
-------------------
5 4
4 8
3 16
2 32
1 64

Proceeding in a similar manner with (3, 5) and (5, 7), I get:

3 5 7
-------------------
20 4
19 8
...
1 2^21
2^22 128
2^22-1 2^8
...
1 2^(2^22+6)

Finally, the biggest number I get – with a single prime factor 7 – is 7^(2^(2^22+7)).

Title: Re: A rather unusual sequence
Post by SMQ on Apr 8^th, 2005, 6:30am

Quote:

(probably, SMQ had in mind this part that was programmed)

Exactly. My program has been evolving over the course of this thread, both in methodology (the first version took >30min. to calculate a₁₂) and in numerical representation (from machine ints to unlimited precision ints to prime factorizations, and now to some sort of algebraic power series representation for powers of prime factors, I'm thinking) but it's basic steps have remained the same:

For each n from 1 to some upper limit
. For each possible set S₀ of composities chosen from {C: 4 <= c <= n and c not prime}
. . For i from 1 until no further progress is possible
. . . Recursively construct from set S_i-1 a new n-primitive set S_i with largest member > the largees member of s_i-1

Up until now the program has considered all possible s_i in the innermost construct, but a₁₄ makes that impractical (to say the least!), so now that we appear to have the basic pattern I'm going to apply that construction so that the program only needs to consider all combinations of prime factors (a *much* smaller set than all possible products of all combinations of all powers of prime factors) at each step.

My chalange now is in finding a machine representation of very large numbers (like 7^2^(2^22+7)) that still allows, at the least, efficient comparison of magnitudes (so that it can check that the new element being considered is indeed > the largest in S_i-1), and preferably efficient algebraic operations as well. Which, since I do have a day job, will probably have to wait until the weekend...

--SMQ

Title: Re: A rather unusual sequence
Post by SMQ on Apr 8^th, 2005, 7:14am

OK, one more tweek to a₁₄:
14 | 2 3 5 7 ---------------------- 6 | 1 1 . . 10 | 1 . 1 . 12 | 2 1 . . 14 | 1 . . 1 ---------------------- 315 | . 2 1 1 3675 | . 1 2 2 | . 5 . 4 | . 10 . 3 | . 20 . 2 | . 40 . 1 | . 80 4 . ... | . 1 2^81 . | . . 2^82 14 ... | . . 1 7*2^2^82 | . . . 7*2^(2^82+1)
a₁₄ = 7^(7*2^(2^82+1))

--SMQ

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 9^th, 2005, 4:51pm

Nice - looks like you guys have "sorta" found the major improvement I was talking about.

Here are some hints:

1. Okay, you've realized that 6 allows you to start with 315 as the first odd number rather than 105. But you can get more mileage out of that than you're getting.

2. Your algorithm is basically "one way" - going "both ways" seems unproductive, but it helps a little bit.

3. You've probably noticed that there are some random choices being made, although I guess you need to get #1 and #2 before you can really settle this.

4. This is minor, but be sure you've exhausted all possible continuations!

If a₁₄ is getting boring - what is the general behavior of a_n? Not to the detail we're doing a₁₄, of course - just an approximation.

Title: Re: A rather unusual sequence
Post by SMQ on Apr 11^th, 2005, 8:17am

I don't know about Barukh, but a₁₄ is still holding my interest. :) How's this:

[hideb]a14 | 2 3 5 7 -------------------------- 6 | 1 1 . . 10 | 1 . 1 . 12 | 2 1 . . 14 | 1 . . 1 -------------------------- 315 | . 2 1 1 525 | . 1 2 1 5145 | . 1 1 3 | . 6 . 6 | . 5 . 12 | . 4 . 16 | . 3 . 17 | . 2 . 18 | . 1 . 19 | . 27 . 5 | . 54 . 4 | . 108 . 3 | . 216 . 2 | . 432 . 1 | . 864 5 . | . 884 4 . | . 886 3 . | . 888 2 . | . 890 1 . | . 863 20 . | . 862 5*2^3 . | . ... ... . | . 2 5*2^863 . | . 1 5*2^864 . | . 5*2^865 109 | 5*2^865+4830 108 | . . ... ... | 5*2^865+5044 2 | 5*2^865+5046 1 | . 5*2^865-1 6104 | . 5*2^865-2 763*2^4 | . . ... ... | . . 2 763*2^(5*2^865) | . . 1 763*2^(5*2^865+1) | . . . 763*2^(5*2^865+2)
a₁₄ = 7^(736*2^(5*2^865+2))
[/hideb]
I think that covers hints 1 and 2 (and 4?). As to hint 3, I still found the best case in this pattern through trial and error rather than insight... I could probably do a₁₈ and a₂₀ this way, but a₂₂ would be a whole new can of worms. ;)

So, what am I/are we still missing? ;D

--SMQ

Title: Re: A rather unusual sequence
Post by SMQ on Apr 11^th, 2005, 10:28am

Or, for a whopping 1.65% improvement:

[hideb] a14 | 2 3 5 7 ------------------------------ 6 | 1 1 . . 10 | 1 . 1 . 12 | 2 1 . . 14 | 1 . . 1 ------------------------------ 315 | . 2 1 1 735 | . 1 1 2 2625 | . 1 3 1 | . 6 6 . | . 5 12 . | . 4 19 . | . 3 20 . | . 2 21 . | . 1 22 . | . 27 5 . | . 54 4 . | . 108 3 . | . 216 2 . | . 432 1 . | . 864 . 5 | . 890 . 4 | . 892 . 3 | . 894 . 2 | . 896 . 1 | . 863 . 20 | . 862 . 5*2^3 | . ... . ... | . 2 . 5*2^863 | . 1 . 5*2^864 | . . 121 5*2^865 | . . 120 5*2^865+6083 | . . ... ... | . . 2 5*2^865+6201 | . . 1 5*2^865+6202 | . . 7502 5*2^865-1 | . 3751*2^2 5*2^865-2 | . . ... ... |3751*2^(5*2^865-2) 2 |3751*2^(5*2^865-1) 1 | 3751*2^(5*2^865) .
a₁₄=5^(3751*2^(5*2^865))[/hideb]

--SMQ

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 11^th, 2005, 5:22pm

Good job, you got #2! I feel that you're still missing 1,3, and 4, but I'm not sure if 1 or 3 is the main culprit - it's a little of each. I'll give a hint later if you're still stuck. ;D

Oh, and thanks Barukh for hte nice explanation! :)

Title: Re: A rather unusual sequence
Post by SMQ on Apr 11^th, 2005, 7:33pm

OK, one more attempt, then a) I have to go to bed, and b) I think it's about time somebody else took a shot at it again. ;D

[hideb] a14 | 2 3 5 7 ------------------------------ 6 | 1 1 . . 10 | 1 . 1 . 12 | 2 1 . . 14 | 1 . . 1 ------------------------------ 315 | . 2 1 1 | . 1 2 2 | . 1 4 1 | . 1 1 5 | . . 9 10 | . . ... ... | . . 1 52 | . . 54 9 | . . ... ... | . . 27*2^9 1 | . 7 27*2^10 . | . ... ... . | . 1 x . | . 35 27*2^10-1 . | . ... ... . |35*2^(27*2^10-2) 1 . |35*2^(27*2^10-1) . 422 | . ... . ... | . y . 1 35*2^(27*2^10-1)-1 . 89675 | . ... . ... | . 1 . 89675*2^(35*2^(27*2^10-1)-2) | . . . 89675*2^(35*2^(27*2^10-1)-1)
a₁₄ = 7^(89675*2^(35*2^(27*2^10-1)-1))
= 7^(89675*2^(35*2^27647)-1)
[/hideb]

--SMQ
(edited to fix miscalculation)

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 11^th, 2005, 8:04pm

Good, you're almost there! ;D I'd say you've gotten #1, so it's mainly just picking the right order now.

Quote:

I think it's about time somebody else took a shot at it again.

I think we've successfully scared off everyone else, except maybe Barukh. :P

Title: Re: A rather unusual sequence
Post by Barukh on Apr 11^th, 2005, 11:43pm

on 04/11/05 at 20:04:40, Deedlit wrote:

I think we've successfully scared off everyone else, except maybe Barukh. :P

You certainly haven't scared me. I follow SMQ's heroic attempts to get to the optimal solution, but do not find the power to take the flag.

Maybe, the most interesting question remained is: how do you know that you've got THE optimal answer?

Title: Re: A rather unusual sequence
Post by SMQ on Apr 12^th, 2005, 7:29am

OK, my final (?) attempt at a₁₄, with the reasoning for my decisions at each point:

a) S₀, the subset of S with elements <= n, is chosen to contain all possible multiples of 2 with any other single prime factor (to any power). (i.e. 18 = 2*3*3 would be a good choice for n >= 18, but 30 = 2*3*5 would not be a good choice for n >= 30 because it contains more than one factor > 2.) This choice allows maximum flexibility in the later steps while providing as many occurrances of prime factors > 2 as possible.

a14 | 2 3 5 7 ------------------------------- 6 | 1 1 . . 10 | 1 . 1 . 12 | 2 1 . . 14 | 1 . . 1

b) The rest of the steps then procede by choosing combinations of the prime factors > 2 to manipulate. They are chosen in order of drecreasing number of factors they contain. So for a₁₄ we first choose to manipulate the set of all three factors > 2, then the three sets of 2, then ultimately the three sets of 1 (although in practice 2 of the final 3 sets contribute nothing to the solution)

315 | . 2 1 1

c) Within a set, procede as in b) working progressively smaller sets of factors

| . 1 2 2

d) At this point there is an apparently random choice--we can pick either 5 or 7 for the next step. Looking ahead we see that there is a slight advantage to having the largest power as far to the left as possible, so we choose to manipulate 7 first, then 5.

| . 1 1 4 | . 1 5 1

(continued)

Title: Re: A rather unusual sequence
Post by SMQ on Apr 12^th, 2005, 7:48am

(continuing)

e) We have now exhausted all possible manipulations with three factors so we move on to groups of 2. Since we're building a power tower, any advantage we can gain in the early steps (near the top of the tower) swamps what we may have to give up in exchange in later steps. At each step we want to work with the two (available) factors with the largest powers.

| . . 10 9

f) We procede by decrementing first factor with the smallest power, then the one with the largest. If the two largest have the same powers, we decrement the one on the right first.

| . . ? 8 | . . ? 7 | . . ? 6 | . . ? 5 | . . ? 4 | . . ? 3 | . . ? 2 | . . ? 1

g) But what values should we assign to the other factor at this point? If we naively double it each step we encounter a problem when we go to decrement the other factor: the largest possible choice is smaller than the last step from part f) above. So instead we look ahead to the first step of the second factor:

| . . 9 54

and choose the largest power in part f) smaller than this. (This is why we wanted the larger power on the left--it allows us to choose a higher power here than if the factors are reversed.)

| . . 73 1

Now we can work backwards from this point, choosing at each step the largest possible power which gives a result smaller than the last. Together steps e), f) and g) look like this:

| . . 10 9 | . . 20 8 | . . 40 7 | . . 63 6 | . . 65 5 | . . 67 4 | . . 69 3 | . . 71 2 | . . 73 1

h) Now we can go ahead and do the second decrement. In this case we don't have to worry about the result being too big so we can just double the other power at each step.

| . . 9 54 | . . 8 108 | . . ... ... | . . 2 6912 | . . 1 13824

(continued)

Title: Re: A rather unusual sequence
Post by SMQ on Apr 12^th, 2005, 8:03am

(continuing)

i) Next procede to the other two combinations of 2 factors from the three, choosing at each step the factors with largest powers which haven't yet been used together, first decrementing the smaller power

| . 7 . 27648 | . 6 . 27648+13 | . ... . ... | . 2 . 27665 | . 1 . 27666

then the larger

| . 35 . 27647 | .35*2^1 . 27646 | . ... . ... | 35*2^27645 . 2 | 35*2^27646 . 1

and then the remaining pair, smaller power

| 35*2^27647 533 . 35*2^27647+209198 532 . | . ... ... . 35*2^27647+209258 2 . 35*2^27647+209260 1 .

then larger

|35*2^27647-1 142844 . |35*2^27647-2 35711*2^3 . | . ... ... . | . 2 35711*2^(35*2^27647-1) | . 1 35711*2^(35*2^27647)

j) Finally we consider the three factors in isolation. Since we are only interested in the largest possible member of the set S, we need only consider the factor with the largest power at this step, and the size of the power far outweighs the size of the factor itself, so even though our early choices led us to a final answer which is a power of 5 rather than of 7, the increased power easily makes up for it.

| . . 35711*2^(35*2^27647+1)

giving us a final answer of a₁₄ = 5^(35711*2^(35*2^27647+1))

Now, since I've proven myself fully fallible, what am I still missing? And, as Barukh asked, is there any way to *know* you've found the best solution short of being very methodical in the early stages, for instance while I think we've now thoroughly explored the manipulation of pairs of factors, this example sheds only a little light on combinations of 3 or more factors. I guess I'll have to go and explore a₂₂
;D

--SMQ

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 12^th, 2005, 8:23am

on 04/11/05 at 23:43:01, Barukh wrote:

Maybe, the most interesting question remained is: how do you know that you've got THE optimal answer?

That's an excellent question, one for which I don't have an excellent answer. Not only do I not have a proof that my number is optimal, I don't have an upper bound of any kind whatsoever! :-[ I suppose that's the biggest problem remaining: Find a reasonable upper bound for a_n (or a₁₄ for starters).

I guess I've been talking like I had the optimal solution, and I'm pretty sure that it is, but you never know!

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 12^th, 2005, 8:29am

on 04/12/05 at 07:29:00, SMQ wrote:

OK, my final (?) attempt at a₁₄,

Nonsense! ;D

Quote:

So for a₁₄ we first choose to manipulate the set of all three factors > 2, then the three sets of 2, then ultimately the three sets of 1 (although in practice 2 of the final 3 sets contribute nothing to the solution)

Aha! This is what I meant when I said you weren't getting full mileage out of the extra 3 - there are really four factors, and the fourth doesn't need to be treated differently from the other three.

Title: Re: A rather unusual sequence
Post by SMQ on Apr 12^th, 2005, 8:48am

Quote:

there are really four factors, and the fourth doesn't need to be treated differently from the other three.

Oookkaaaayyy, but isn't *any* combination of factors including 2 going to be divisible by either 6, 10, or 14? (And leaving even 6 out of S₀--let alone 10 or 14--leads to reduced performance as noted earlier in the thread.)

I mean I could go and add "128 | 7 . . .", but that doesn't contribute anything to the later stages, and any other combination involving a factor of 2 has already been "used" by including 6, 10, and 14 in S₀, right? Am I missing something obvious there, because I've done a lot of abortive attempts along those lines just to later catch the divisibility problem...

--SMQ

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 12^th, 2005, 9:07am

I meant the four factors are 3,5,7, and... 3 again. You're treating one of the threes a little differently from the other factors.

Title: Re: A rather unusual sequence
Post by SMQ on Apr 12^th, 2005, 12:48pm

Hmm, still chewing on that one... meanwhile, looking ahead, with my deepening understanding of the process a₂₂ scares me. ;D

Where a₁₄ has something like 5 separate combination stages (maybe a few more, depending on what Deedit's latest hint means), it looks like a₂₂, with its extra degree of freedom, may well have something like a₁₄ stages! (Not a₁₄, specifically, but the process which generates stages in a₂₂ is beginning to feel a lot like the process which generates the result for a₁₄...)

--SMQ

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 12^th, 2005, 6:16pm

In case you are having trouble describing some of these numbers, I present the Ackermann function:

A₁(n) = 2n

A_m(n) = A_m-1ⁿ (1) = A_m-1(A_m-1(...A_m-1(1)...)) (n copies)

So for instance, we get A₂(n) = 2*2*2...*2 = 2ⁿ. And A₃(n) = 2^(2^(...(2^2)...)) with n copies of 2. A₄(n) will help you when you find yourself saying, "Okay I want a tower of exponents - but to describe the number of exponents, I'm going to need another tower - and that number of exponents needs its own tower...".

There are actually several different versions of Ackermann's function; I also like this "wolf-in-sheep's clothing" variant:

A(0,n) = n+1
A(m+1,0) = A(m,1)
A(m+1,n+1) = A(m, A(m+1,n))

Looks harmless, but the growth rate is astounding!

Title: Re: A rather unusual sequence
Post by SMQ on Apr 13^th, 2005, 6:10am

I'd forgotten about Ackermann's function, which might apply nicely here because it's based on 2's, but I've always had an interest in very large numbers and am reasonably comfortable with Knuth's up-arrow notation:

2^3 = 2^3
2^^3 = 2^²3 = 2^2^2
2^^^3 = 2^³3 = 2^^2^^2
etc.

which is closely related to numbered power operators:

2⁽¹⁾3 = 2+3
2⁽²⁾3 = 2*3 = 2+2+2
2⁽ⁿ⁾3 = 2^^n-23

and for *really* large numbers there's always Conway's chained arrow notation:

2-->3-->n = 2^ⁿ3 with rules for longer chains such that 2-->3-->p-->q can comparcly represent 2^ⁿ3 where n is itself a very large number.
http://planetmath.org/encyclopedia/ConwaysChainedArrowNotation.html

I can't speak for others following this thread, but notation isn't my fear with a₂₂; it's being at all sure I'm covering all the possibilities without actually working out all ~2^^6 steps. ;D

Meanwhile, I still have no clue where your last hint is pointing ???, but I'm not giving up on a₁₄ just yet. I'm going to owe my employer a vacation day or two for this problem, though. ;)

--SMQ

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 13^th, 2005, 9:49pm

on 04/13/05 at 06:10:56, SMQ wrote:

and for *really* large numbers there's always Conway's chained arrow notation:

and for even larger numbers, there's extended Ackermann notation:

A(0, ...,0, x₀) = x₀ + 1
A(x_n, ..., x₁ + 1, 0) = A(x_n, ..., x₁, 1)
A(x_n, ..., x_i + 1, 0, ..., x₀) = A(x_n, ..., x_i, x₀, ..., 0)
A(x_n, ..., x₁ + 1, x₀ + 1) = A(x_n, ..., x₁, A(x_n, ..., x₁ + 1, x₀) )

But, I'm getting ahead of myself.,, ;D

Quote:

I can't speak for others following this thread, but notation isn't my fear with a₂₂; it's being at all sure I'm covering all the possibilities without actually working out all ~2^^6 steps. ;D

Well, I'm not totally sure either... I'm also not optimistic that we can prove the actual maximums; all I'd like is to prove a reasoable upper bound. (but I don't even have that :'( )

Quote:

Meanwhile, I still have no clue where your last hint is pointing ???, but I'm not giving up on a₁₄ just yet.

I was referring to the order you took things in; you took numbers with all 3 factors first, then numbers with 2, then with 1, but why?

Quote:

I'm going to owe my employer a vacation day or two for this problem, though. ;)

Good lord! I didn't mean to cause that. :-[

Title: Re: A rather unusual sequence
Post by SMQ on Apr 14^th, 2005, 5:51am

on 04/13/05 at 21:49:38, Deedlit wrote:

all I'd like is to prove a reasoable upper bound. (but I don't even have that :'( )

Hmm, I'll have to see what you've got for a₁₄, but I think I'm getting close to somewhat-reasonable upper (and, maybe, lower) bounds by extending my last stated approach to a₁₄ to greater degrees of freedom.

Quote:

you took numbers with all 3 factors first, then numbers with 2, then with 1, but why?

Because introducing a number with fewer factors before a number with more factors limits the possibilities more than the reverse. I guess I'm just not sure what you mean by using "all four factors"--I could write

3 3 5 7 ------- 1 1 1 1 1 . 2 2 . 1 1 4 . 1 5 1

but that's really the same thing as before, and I'm not finding any other options that don't limit one of the later 2-factor stages...

[quote]Good lord! I didn't mean to cause that. :-[/quote]
Don't worry, it's not your fault! It's just that this problem is at least an order of magnitude more interesting than the code I'm writing for work--so what would otherwise be a 5-minute break somehow becomes half an hour... Besides, I've got the vacation time to spend. ;D

--SMQ

Title: Re: A rather unusual sequence
Post by Barukh on Apr 14^th, 2005, 10:58pm

Deedlit, I'm curious: what is the source of this problem?

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 15^th, 2005, 3:06pm

on 04/14/05 at 05:51:35, SMQ wrote:

Because introducing a number with fewer factors before a number with more factors limits the possibilities more than the reverse.

Well, that's not quite true. I'll spill the beans in a couple days, but I'll let you stew over it a little longer. :P

Quote:

I guess I'm just not sure what you mean by using "all four factors"--I could write

3 3 5 7 ------- 1 1 1 1 1 . 2 2 . 1 1 4 . 1 5 1

but that's really the same thing as before, and I'm not finding any other options that don't limit one of the later 2-factor stages...

No, that's not it. I guess what I said isn't really helping. Basically, just try to put the stages in a different order.

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 15^th, 2005, 3:23pm

on 04/14/05 at 22:58:12, Barukh wrote:

Deedlit, I'm curious: what is the source of this problem?

It's modified from a problem in Harvey Freidman's lecture "Enormous Integers in Real Life." You can get the lecture notes, along with lots of other fascinating stuff, from his web page:

http://www.math.ohio-state.edu/%7Efriedman/manuscripts.html

In his original version, numbers are allowed to be multiples of numbers below k. I modified it so that the sequence didn't jump until 14, rather than 7 - it made it a little more surprising, I thought.

There are a whole bunch of similar problems in that paper (and also in "Lecture Notes on Enormous Integers"). The problems on Bolzano-Weierstrauss and algebraic supersets are especially surprising, in that you can't see the combinatorial structure at first glance the way you can in the other problems.

Some other interesting papers on the site talk about some amazing independent results - some theorems that deal with just finite numbers and structures, but are not only independent of ZFC, but even ZFC plus large cardinal axioms!

Title: Re: A rather unusual sequence
Post by SMQ on Apr 18^th, 2005, 7:14am

on 04/15/05 at 15:06:12, Deedlit wrote:

Quote:

Because introducing a number with fewer factors before a number with more factors limits the possibilities more than the reverse.

Well, that's not quite true. I'll spill the beans in a couple days, but I'll let you stew over it a little longer. :P

Hmm, I think after my past week's experimentation I'm going to stand behind my assertion--I look forward to your "solution." ;D ;D

(Tounge firmly in cheek for the humor impaired!)

--SMQ

Title: Re: A rather unusual sequence
Post by Barukh on Apr 18^th, 2005, 10:24am

on 04/15/05 at 15:23:12, Deedlit wrote:

Very interesting stuff indeed (although not an easy reading). Thanks for the reference.

Frankly speaking, I couldn’t recognize the origin of this problem in above notes. Did you modify it so it became unrecognizable, or I was looking at the wrong paper?

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 18^th, 2005, 12:35pm

on 04/18/05 at 10:24:03, Barukh wrote:

Very interesting stuff indeed (although not an easy reading). Thanks for the reference.

You're welcome. Also, take a gander at some of the large cardinal papers, like "Finite Trees and the Necessary Use of Large Cardinals". The proofs may be too much but the theorems themselves are amazing! :o

Quote:

Frankly speaking, I couldn’t recognize the origin of this problem in above notes. Did you modify it so it became unrecognizable, or I was looking at the wrong paper?

It's #7 - it's pretty close to what I wrote. Note that his values for #(5) and #(6) are wrong, and his bound for #(7) is overly low.

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 18^th, 2005, 1:43pm

SMQ: Here's what I have; I'm borrowing your table.

a14 | 2 3 5 7 ------------------------------ 6 | 1 1 . . 10 | 1 . 1 . 12 | 2 1 . . 14 | 1 . . 1 ------------------------------ 315 | . 2 1 1 | . 4 2 . | . 3 4 . | . 2 8 . | . 13 1 . | . 26 . 2 | . 32 . 1 | . 25 . 5 | . 24 . 10 | . ... . ... | . 2 . 5*2^23 | . 1 17 5*2^24 | . 1 16 5*2^24 + 123 | . 1 ... ... | . 1 1 5*2^24 + 138 | . 1 170 5*2^24 - 1 | . 1 ... ... | . 1 170*2^(5*2^24-1) . | . . 170*2^(5*2^24) 25*2^47 + 175*2^23 + 2088 | . . ... ... | . . 1 (25*2^47 + 175*2^23 + 2088 ) * 2 ^ (170*2^(5*2^24) - 1) | . 1 0 (25*2^47 + 175*2^23 + 2088 ) * 2 ^ (170*2^(5*2^24) ) | . . . (25*2^47 + 175*2^23 + 2088 ) * 2 ^ (170*2^(5*2^24) + 1)
a₁₄ = 7 ^ (25*2^47 + 175*2^23 + 2088 ) * 2 ^ (170*2^(5*2^24) + 1)
= 7 ^(351848676891688 * 2 ^ (170 * 2 ^ 83886080 + 1)) > 10 ^ 10 ^ 10 ^ 25252228.

Title: Re: A rather unusual sequence
Post by SMQ on Apr 18^th, 2005, 2:03pm

Hot smoke in a bucket!:o

Looks like I need to take my undergrad math minor and my computer and head back over to medium to work on some chess probabilities. ;D

Seriously, though, that's slick, and I completely missed it. Now to try to generalize that algorithm and work out something like reasonable bounds...

--SMQ

Title: Re: A rather unusual sequence
Post by Deedlit on Apr 19^th, 2005, 3:21am

Nah, you got very close - closer than I expected anyone to get, actually! :D (Unless, of course, I'm not very close. :P)

Title: Re: A rather unusual sequence
Post by Barukh on Apr 19^th, 2005, 8:28am

on 04/18/05 at 13:43:32, Deedlit wrote:

SMQ: Here's what I have;

Deedlit, your solution is really impressive! I have a couple of questions, though:

Quote:

a14 | 2 3 5 7 ----------------------------- | . 26 . 2 | . 32 . 1 | . 25 . 5 | . 24 . 10

Is it correct that 32 in the second line may be replaced by any number in the interval [27,52]? Not that is changes something…

Quote:

a14 | 2 3 5 7 ----------------------------- | . 1 17 5*2^24 | . 1 16 5*2^24 + 123 | . 1 ... ... | . 1 1 5*2^24 + 138 | . 1 170 5*2^24 - 1 | . 1 ... ... | . 1 170*2^(5*2^24-1) .

Where does this 123 term come from? Can’t it and all successive additions be increased, making the final solution even more horrible?

Title: Re: A rather unusual sequence
Post by SMQ on Apr 19^th, 2005, 11:12am

The answer to both questions springs from the same source: the first number of the *next* series needs to be larger than the last number of this series.

In the first case, any power of 3 >32 leads to 3ⁿ*7¹ > 3²⁵*7⁵, and that's a no-no.

In the second case, it's the 5*2²⁴+138 that's the similarly limited power, but each preceding power needs to be less than the next, so the sequence can't start >5*2²⁴+123.

Hope that made sense.

--SMQ