| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1333.1 | The sequence is constant modulo 9 | DECWET::BISHOP | Avery: father, hacker, brewer, Japanese speaker | Fri Nov 09 1990 14:19 | 20 |
| >It is not a big deal to check it with a computer on all the potential
>starting values. The number of cases can even be reduced by symetry,
>congruence and more sophisticated tricks. But the few proofs I have seen
>so far all seems to end up to be of the one-by-one-check-on-a-large-list
>type. Which certainly proves the fact but leaves a flavour of unexplained.
I take it you are not asking for a proof, since you've seen more than one.
The problem is that the only _rigorous_ answer to the question "why" in
mathematics is a proof. What you want is an intuitive explanation, right?
Here's an attempt:
When you exchange the digits in a base ten representation of a number, the new
number is equivalent to the old one modulo 9. Any unique mapping of a finite
set (e.g., the 4 digit numbers equivalent to n mod 9) into itself has to cycle
at some point when repeatedly applied. In this case, there are only a small
number of possible 4 digit numbers of a given value mod 9 through which the
numbers can cycle, so it is begins to cycle quickly.
Avery
|
| 1333.2 | What is "stabalizes". | CADSYS::COOPER | Topher Cooper | Fri Nov 09 1990 16:11 | 18 |
| RE: .1 (Avery)
More specifically, since the "increasing ordered" and the "decreasing
ordered" versions have the same digits, they are equivalent mod 9,
hence their difference will be zero mod 9. After the first iteration,
therefore, the numbers will all be divisible by 9.
I'm not sure what is meant specifically by "stabalizes". If it just
means "settles into a cycle" then that is, as was pointed out,
inevitable because there are only a finite number of values. If it
means "settles into a short cycle" then that may simply be because with
only 40 or so relevant sets of 4 digits, a long cycle is unlikely. If
it means "settles into a cycle of one", then it may simply be a
coincidence for base-10 and 4 digits (not an outlandish one given the
previous), or there may be something deeper going on. What happens
with other bases/number of digits?
Topher
|
| 1333.3 | 6174 = 2 * 3 * 3 * 7 * 7 * 7 | VMSDEV::HALLYB | The Smart Money was on Goliath | Fri Nov 09 1990 16:26 | 7 |
| I tried a few examples by hand and got 6174 each time. (Hmmm, that
makes 6174 an "interesting" number).
Working in octal I found a five-element orbit starting with 1776, so
"convergence" to a specific number seems to be a coincidence.
John
|
| 1333.4 | | GUESS::DERAMO | Dan D'Eramo | Fri Nov 09 1990 16:37 | 14 |
| >> I tried a few examples by hand and got 6174 each time. (Hmmm, that
>> makes 6174 an "interesting" number).
:-)
>> Working in octal I found a five-element orbit starting with 1776, so
>> "convergence" to a specific number seems to be a coincidence.
So that's why Independence was declared then! :-)
Notice, the digits still sum to a multiple of one less than
the base.
Dan
|
| 1333.5 | 0000 = 0 | CADSYS::COOPER | Topher Cooper | Fri Nov 09 1990 17:28 | 9 |
| RE: .3 (John)
> I tried a few examples by hand and got 6174 each time. (Hmmm, that
> makes 6174 an "interesting" number).
Without trying any, though, there is at least one other "cycle of 1",
to wit 0000, which can be reached from 1111, 2222, 3333, etc.
Topher
|
| 1333.6 | Good point ... | DECWET::BISHOP | Avery: father, hacker, brewer, Japanese speaker | Fri Nov 09 1990 20:38 | 12 |
| RE: .2 (Topher)
> More specifically, since the "increasing ordered" and the "decreasing
> ordered" versions have the same digits, they are equivalent mod 9,
> hence their difference will be zero mod 9. After the first iteration,
> therefore, the numbers will all be divisible by 9.
Yes, that's the real point. I only thought about it long enough to realize
that they were equivalent mod 9, but missed the fact that that makes their
difference 0 mod 9.
Avery
|
| 1333.7 | The problem was divided by 100 | SHIRE::ALAIND | Alain Debecker @GEO DTN 821-4912 | Mon Nov 12 1990 06:20 | 26 |
| Re.4
> Notice, the digits still sum to a multiple of one less than
> the base.
Moreover this is independant of the base. And of the number
of digits.
Take a number x, writen x = a*p^3 + b*p^2 + c*p + d in base p,
supposing a>b>c>d for convenience. Sorting-substracting gives
f(x) = (p^3-1)*(a-d) + (p^2-p)*(b-c)
From which (p-1) factors out. Note that the same will hold for
any number of digits. This means that f(x) is a multiple of p-1,
and proves Dan's.
In case p=10 you get f(x) = 9*(111*(a-d) + 10*(b-c)). As a-d and
b-c can only take 10 values each, it reduces to p*p = 100 cases.
More generaly it shows that the maximum cycle order is less than
p*p (or p^s in case of 2s or 2s-1 digits).
Going further would requires (1+p), (1+p+p^2),... (1+p+...+p^s)
relatively prime. But:
1) Usually the cycles are much shorter,
2) 6174 is still an "interesting" number,
3) I don't believe in computer's prooves, even on 100 cases,
4) What's the fractal structure of the orbits ?
|