Operation Kaprekar

January 13, 2007 10:19 PM

Mysterious number 6174. An excellent recreational math article.
posted by fatllama (34 comments total)

Mysterious number 6174 indeed.
MeFi: 0 posts RSS feed of posts by johnny2001, 0 comments
MetaTalk: 0 posts RSS feed of posts by johnny2001, 0 comments
Ask MeFi: 0 questions RSS feed of posts by johnny2001, 0 answers
Music: 0 songs RSS feed of music posts by johnny2001, no comments, no playlists
Projects: 0 posts.
posted by ibmcginty at 10:30 PM on January 13, 2007

yeah, what is UP with that guy??!
posted by empath at 10:41 PM on January 13, 2007

Damnit, someone has been raiding my bookmarks again! Well done!

*scratches one more off the list from his pool of MeFi-quality links, moves on to the next one*
posted by loquacious at 10:47 PM on January 13, 2007

yeay, my IQ went up a point reading that. Tx.
posted by Heywood Mogroot at 10:58 PM on January 13, 2007

Numerology rocks! Once you take out the hocus-pocus, becoming one with god crap.
Mathmatics has much more to teach us.

ALL BOW DOWN BEFORE THE MATH!
posted by Balisong at 11:17 PM on January 13, 2007

"That's all well and good, but with my new Theorem(tm), you too can understand the right triangle!"
--Pythagoras
posted by Balisong at 11:19 PM on January 13, 2007

I'd hoped this was going to be a recreational METH problem.

"Your usual dealer is out of town, and so the choices are you can buy from Lefty, whose shit is weak but he will definitely have it, or you can score from Z-Dog, who gets the good shit, but half of the time, doesn't have it.

Using game theory, articulate your best strategy for getting high in this context?"
posted by PeterMcDermott at 1:48 AM on January 14, 2007

Bam. Proof of the Creator. Thanks!
posted by dozo at 1:49 AM on January 14, 2007

I think the main problem here is the term "recreational math". Of all the things I could do with my time off, math(s) ranks up there with self-immolation.
posted by TheDonF at 4:42 AM on January 14, 2007

I find his use of the the word "kernel" a little nonstandard, and would rather call numbers such as 6174 that stay fixed under the operation "fixed points." In any case, he doesn't call much attention to some of the more interesting questions that seem to leap out immediately to me, like:

1. The numbers 2,5, and 7 seem particularly wonderful as lengths which don't have any fixed point under the K. operation. Why 2, 5, and 7? Are there lots of such lengths, or only a few?

2. 6174 and 495 are clearly the first entries in two infinite families of fixed points (6174, 631764, 63317664,... and 495, 549945,554999445,..., respectively). How many such families are there? Does every fixed point give rise to an infinite family of fixed points by some sort of expansion process like this, or are there sporadic examples? The sporadic examples would be quite special - how many might there be, if any?

3. The operation can be done just as well with bases other than 10. What are the fixed points in binary? Are there numbers that are fixed in every base? In no base? Are there bases with a fixed point of every length, or bases in which there are never fixed points?

4. Can the (decimal, say) operation be extended smoothly to a real function for which the usual differential machinery for studying fixed points can be applied? I can imagine extending the operation to numbers with a terminating decimal expansion, certainly; since those numbers are dense in the reals there would be a unique continuous extension if there is one at all. (But there probably isn't, now I think about it - at least for my naive guess at how to operate on decimals).

And that barely scratches the surface of what you could ask if you really thought about it. This is why mathematics is recreational - you think it's already all been done, put in book and just there to be recited & absorbed? Not at all. There are always new areas of the playground that no-one's ever even touched before, and they open up on new areas, and so on ad infinitum.
posted by Wolfdog at 6:14 AM on January 14, 2007

I find it interesting that numbers with 5 digits are condisered "disappointing" because they don't have a single fixed point, but have a set of closed orbits instead. That has to be related to the fixed point phenomenon as well. There must be numbers where there is both no fixed point and no orbits as well. Sort of like the points outside the Mandelbrot set.
posted by jimfl at 6:26 AM on January 14, 2007

Not so, jimfl, because there's only a finite set of 5-digit numbers. Same goes for n-digit numbers. So any number will eventually end up in a cycle.
posted by Wolfdog at 6:31 AM on January 14, 2007

(The numbers outside the mandelbrot set "go off to infinity", which isn't possible when you're working with a compact domain. If you compactify the complex numbers to form the Riemann sphere, then you can look at 8734; as an attracting fixed point which all those "bad" points are getting sucked toward. There are other compactifications which would be a little more discriminatory in how they regard those trajectories.)
posted by Wolfdog at 6:35 AM on January 14, 2007

Excellet post fatllama, I'm on my second cup of coffee reading it. Thanks!
posted by BillsR100 at 7:47 AM on January 14, 2007

Fascinating. Doesn't this make 6174 one of the building blocks of the universe? Is it the meaning of life in numeric form? It spells out FAGD if each number is turned into it's alpha equivalent and that has to be an acronym for something huge (or molecular)...hmmm? Fly All Good Doggies? Film at Geodesic Delights?
posted by Skygazer at 8:45 AM on January 14, 2007

The big number adds down to three to the third power, and the 3 digit number adds down to three to the third power as well, the two digit number chosen offers various powers of three, though it didn't start out divisible by three. All the variants of the two digit version add up to three squared. Something about the operation converts base 10, to base three maybe. That is a big maybe.
posted by Oyéah at 8:52 AM on January 14, 2007

All the kernels are multiples of 9.

I call that if you figure the puzzle out and win the Nobel prize because of my clue, I get a cut.
posted by jewzilla at 10:01 AM on January 14, 2007

Oyeah, any number that is base 3 or a factor of 9 seems to add up to variants of 9. For example, 3^5=243, and 2+4+3 adds to 9, or 9x12=108, 1+0+8=9. Or, 9x401=3609, 3+6+0+9=18, and 1+8=9. In this case, 6174 divides by nine and adds to 18, which adds to nine. 9x6174=55566, which adds to 27, which adds to 9. I've always wondered about how to prove the relationship, but I had never heard of kernals or 6174.
posted by Brian B. at 10:06 AM on January 14, 2007

The "digit sum" tests for multiples of 3 or 9 are not hard to prove; the wikipedia divisibility tests page has an adequate explanation of why a number is divisible by 3 if and only if the sum of its digits is divisible by 3; and the same idea works for 9. These used to be common grade-school knowledge but I think they're regarded as mere trivia now.

Maybe my favorite divisibility test is the "alternating digit sum" test for divisibility by 11, which is much less commonly known than the tests for 2,3,4,5, and 9. It's explained succinctly at the MathWorld divisibility tests page, and is closely related to the procedure for calculating the checksum digit for ISBNs.

All the kernels are multiples of 9.
This has to be the case - there's a neat fact (no harder to prove than the divisibility test) that the difference between a number and any permutation of its digits will be divisible by 9. A "kernel" of the K. operation is a difference between two permutations of the same digits, so it'll be divisible by 9.
posted by Wolfdog at 10:25 AM on January 14, 2007

Good post, but I'm going to be a wet blanket here.

A lot of functions have fixed points (Wikipedia link)

I haven't analyzed this, but it seems that if I were to just completely randomly map every four (or whatever) digit number to a random four digit number (i.e., just come up with a table with every 4 digit number appearing once in the left column, and just random 4 digit numbers in the right column,) it seems like there is a reasonable chance (call it N) the resulting function would have a fixed point, especially since every number might not appear in the right column (so, your population would tend to decrease each iteration.)

I don't know N (the probability of a random mapping having a fixed point,) but the higher N is, the less remarkable or interesting this finding is.

If this methodology yielded a function which had a fixed point for all number lengths, that would be more interesting, but, alas, it seems not to work for 2 or 5-10. So, it seems like they just rolled the dice, and it came up below N.
posted by blenderfish at 2:15 PM on January 14, 2007

If you multiply 6174 by 666 it equals 4111884.

If you add 4 + 1 + 1 + 1 +8 + 8 +4 = 27!!

27 divided by 3 (the trinity!!) you get 9!!

Coincidence. I think not.
posted by Skygazer at 2:16 PM on January 14, 2007

blenderfish, I think your N might be lower than you think. The fixed point would have to map to itself; with 9000 4-digit numbers, a random mapping will only do this 1/9000 of the time. Also, no other numbers can map to themselves, so each of the 8999 others has one fewer choice; already we're down to N <= (8999^8999) / (9000^9000) ~= 4.09e-5. And that doesn't take into account the fact that there can't be loops of any kind, except for the self-loop at the fixed point.

But, yeah, this is some pretty cool stuff; I'm also curious about the other bases...
posted by equalpants at 3:19 PM on January 14, 2007

blenderfish, I think your N might be lower than you think. The fixed point would have to map to itself

Exactly one number would have to map to itself, but it wouldn't have to be a particular number--there are 10000 chances at it.

Okay, so let's do this thing.

There are 10000^10000 possible mappings overall.

There are 9999^9999 possible mappings with the given number X mapping to itself (and no other numbers mapping to it),
and there are 10000 choices of which number X maps to itself.

So, we can construct 10000*(9999^9999) unique mappings which satisfy our requirement.

Since there are (10000^10000) possible mappings total,
the fraction is 10000*(9999^9999)/(10000^10000)

which reduces to:
(9999^9999)/(10000^9999)
which reduces to:
(9999/10000) ^ 9999

Which is 0.3678978, or 36.8%.
So, 36.8% of systems satisfy the requirement that they have exactly one number which maps to itself.


(Minor detail, but since leading zeros are okay in the article, there are 10000 4-digit numbers in the definition we're using. (0000-9999.))
posted by blenderfish at 3:55 PM on January 14, 2007

..as a disclaimer, 36.8% is an upper bound on N, not the value of N.

However, intuitively, to me, it feels like the exact value of N should be at least a couple percent.
posted by blenderfish at 4:03 PM on January 14, 2007

Your count is wrong - an enormous overcount, as most of the maps you construct have other fixed points besides your X; counting the number of maps with precisely a given number of fixed points is a classic and somewhat subtle problem - but it's also beside the point. This is why the two multiplication puzzles are given near the bottom of the article - one of them is simple, elegant, and intrinsically interesting. The other one seems arbitrary and far less worth pursuing. In the same way, the K. operation (I keep reading the name as kerékpár, hence the abbreviation) is simple and elegant and naturally stimulates people to explore its dynamics; "any old map" just won't be as intriguing.
posted by Wolfdog at 4:10 PM on January 14, 2007

Aww, crap, blenderfish, of course you're right--I seem to have switched between counting combinations and permutations somewhere.

But, hey, a better bound shouldn't be too hard. A mapping with a fixed point takes the form of a tree (with an extra self-loop at the root), so let's build the tree randomly: first, choose a node to be the root and add the self-loop. Now go through the other 9999 nodes; at each step, choose one to add to the tree, and then choose a node that's already in the tree to map it to (any node in the tree is fine). This gives us:

N <= (10000 * (9999*1) * (9998*2) * ... * (1*9999)) / 10000^10000

or

N <= (10000 * 2 * 9999!) / 10000^10000 ~= 5.69e-4341

...which is also just an upper bound, because our tree-building procedure can build the same map in multiple ways. But that's a pretty tiny number!
posted by equalpants at 4:33 PM on January 14, 2007

most of the maps you construct have other fixed points besides your X
Wrong. They may have cycles, which would make them not the sort of mapping we're looking for (and this is why this is an upper bound on N, and not exactly N,) but, again, if I pick a one of the values X, the only constraint on the other 9999 values is that they each can't be themselves. So, for each of the 9999 values that are not X, there is 9999 possible values it can be, hence 9999^9999.

Since there are 10000 possible values of X, and there are 10000*(9999^9999) possible mappings with exactly one fixed point. (Though there may be cycles of varying periods, which would, again, make them not suitable for our purposes.)

If you have an alternative counting method which disproves mine somehow, please elaborate.
posted by blenderfish at 4:37 PM on January 14, 2007

Jesus, I should obviously not be doing math today. That should be (9999!)^2, of course, not 9999!*2. Which, unfortunately, gives N <= 8.1e31314, which is no help at all.

I believe I shall go do something which does not require thinking...
posted by equalpants at 4:40 PM on January 14, 2007

Ya, sorry, not sure what I was thinking. The calculation is still missing the point, though.
posted by Wolfdog at 4:56 PM on January 14, 2007

I thought it was interesting that the two digit loop has all the numerals in it once, which gives it a magic square quality. It would be interesting to see what, if any, loops form for the five and 7 digit numbers.

The thing that makes me suspicious is the operation of shuffling the digits in these numbers around like they do. The value of the subtraction operation is only important in reducing the number of digits until only 6174 or 495 remain (it's also interesting that 4 is special survivor). So what is it about these numbers that is important, the value of them, or their order in sequence (which is governed by their value)?

To put it another way, what value relationship does 7641 and 1467 have to 6174 other than 7641 - 1467 = 6174?
posted by wobh at 5:28 PM on January 14, 2007

cute link! (i've noticed that now that fatllama has been doctored up, he's really been hitting mefi with a vengeance)
posted by lester the unlikely at 5:44 PM on January 14, 2007

The Penguin Book of Curious and Interesting Numbers by David Wells is a small encyclopedia of this kind of stuff. Most of the entries are brief. It's a great bathroom reader.
posted by neuron at 6:38 PM on January 14, 2007

I get the point, Wolfdog, I just want to try to figure out exactly how common this property is.

Anyway, I'm going to work on this, and I'll report back when/if I get an exact value for N.

Thanks for the input, equalpants and Wolfdog.
posted by blenderfish at 8:33 PM on January 14, 2007

I enjoyed this. Thanks.
posted by ikkyu2 at 2:16 AM on January 15, 2007