Here is a problem I heard about at the Gathering for Gardner. Is it hard? easy? boring? interesting? I don't know.
Let N={1,2,3,...}
PROBLEM: parameters are s (start point) and f (not sure why to call it f). both are in N
Keep in mind the sequence, in order, of operations:
DIVIDE BY f, SUBTRACT f, ADD f, MULTIPLY by f.
form the following sequence of numbers in N
a(0)= s
Assume a(0),...,a(n) are known. Let A = {a(0),...,a(n)}. N-A are the elements in N that are NOT in A.
If a(n)/f is in N-A then a(n+1)=a(n)/f
Else
If a(n)-f is in N-A then a(n+1)=a(n)-f
Else
If a(n)+f is in N-A then a(n+1)=a(n)+f
Else
If a(n)*f is in N-A then a(n+1) = a(n)*f
Else
If none of the above holds then the sequence terminates.
Lets do an example! Let a=14 and f=2
14, 7, 5, 3, 1, 2, 4, 6, 8, 10, 12, 24, 22, 11, 9, 18, 16, 32, 30, 15, 13, 26, 28, 56, 54, 27, 25, 23, 21,
19, 17, 34, 36, 38, 40, 20, STOP since 10, 18, 22, 40 are all on the list.
Lets do another example! Let a=7, f=2
7, 5, 3, 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 9, 11, 13, 15, 17, ... (keeps going)
If f=2 and you get to an odd number x so that ALL of the odds less than x have already appeared but NONE of the odd numbers larger than x have appeared, then the sequence will go forever
with x, x+2, x+4, ...
QUESTIONS and META QUESTIONS
1) Can one characterize for which (s,f) the sequence stops.
2) Is it decidable to determine for which (s,f) the sequence stops.
3) Both (1) and (2) for either fixed s or fixed f.
4) Are the above questions easy?
5) Are the above questions interesting?
There are four categories:
Easy and Interesting- Hmmm, if its TOO easy (which I doubt) then I supposed can't be interesting.
Easy and boring.
Hard and interesting. This means that some progress can be made and perhaps connections to other mathematics.
Hard and Boring. Can't solve and are not enlightened for the effort.
I just played around with it for a while and I'm a bit confused. Do you know of *any* a and f>2 so that it halts? From what I've seen so far it seems natural to conjecture that f=2 is the only interesting case.
ReplyDeleteA little further update, I'm almost sure it is a trivial question for f > 2. For instance, for f = 3 the outline of the proof is the following.
ReplyDeleteSuppose that the initial a is congruent to 1 mod 3. Then 3 will be subtracted until the value reaches 1, which then produces 3, 6, 2, 5, 8, ... continuing to produce all the numbers equal to 2 mod 3 in order. If the original a is congruent to 2 mod 3, then 3 will be subtracted until the value reaches 2, which then produces 6, 3, 1, 4, 7, ... increasing through all the numbers congruent to 1 mod 3 (although the initial number 2 itself must be special cased: it immediately produces the increasing sequence of all numbers congruent to 2 mod 3).
This only leaves numbers divisible by 3. Notice that the only multiples of 3 that occur in the above are 3 and 6, so any number which is of the form 3^n*k for k with no factors of 3 not equal to 1 or 2 will divide off all the factors of 3 until it reaches the previous cases. The other cases will divide off factors of 3 until they reach either 3 or 6. The sequence for 3 is: 3, 1, 4, 7,... up through all numbers congruent to 1 mod 3 (never hits anything else of the for 3^k afterwards) and the sequence for 6 is: 6, 2, 5, ... up through all numbers congruent to 2 mod 3. In this way we see that for f=3 the sequence never halts and eventually settles into increasing along a residue class.
Numerics strongly imply that these same proofs work for all f > 2. The process will start by removing factors of f. Afterwards, it will subtract down along its residue class mod f until it is one of the numbers 1,...,f-1. Then a small set of cases will eventually shuffle that number into the smallest representative of one of the other residue classes, which will then grown unboundedly. This may even be able to be turned into a proof for arbitrary f>2 directly with a little thought, but I have not done it yet.
f = 1 is of course trivial, This leaves f=2. It seems f=2 can probably be fully analyzed as well, but it seems to be the trickiest.
Great! Thanks!
DeleteOnward to f=2!
I actually played a little more and f=2 is much stranger than I though! I think a good concrete goal to have is to try and understand a=18 and show that it never halts. It does not fall into the cases in the blog post, or what I describe above. The values oscillate wildly, but exhibit some sort of self-similarity (the same pattern gets repeated at twice the scale). It can likely be analyzed, but with a significant effort. Once the behavior of 18 is understood, we might then understand all the behaviors that can occur, although numbers like a=288 show that things can get very wild indeed!
DeleteExcellent!
DeleteAnd goes towards my point of you don't know whats going
to be hard/easy interesting/boring.
Koloth- please email me your email address, something I want to ask you about not-through-comments.
DeleteI like to say that mathematics should be either beautiful or important (or both!). I see a lot of arbitrariness in performing these operations in a fixed sequence, and in the fact that we're multiplying/dividing and adding/subtracting by the same number.
ReplyDeleteIf it secretly comes from a more obviously reasonable problem, or if the solution turns out to be really nice, then I might be able to be turned on to this problem. Otherwise I'd put it in the uninteresting bucket.
A math problem may or may not LOOK interesting and may or may not BE interesting. And there is prob a mild correlation in that those that LOOK interesting are more likely to BE interesting then those that don't.
DeleteAs for the one at hand- the f=2 case SEEMS to be hard to understand and hence SEEMS interesting. Some sequences take a LONG time to terminate, which SEEMS interesting.
Agree that the problem is arbitrary.