Slashdot Mirror
Amateur Quest For Lychrel Numbers
Habberhead writes "Some people are aware of the quest for a palindromic solution for the number 196. Basically any number that doesn't form a palindrome by reversing and adding its digits is known as a Lychrel Number. (Sequence Number A023108 of Sloan's On-Line Encyclopedia of Integer Sequences) The number 196 happens to be the first of them. In over a year's worth of time, and more than 2 quadrillion calculations, this guy at www.p196.org has reversed and added the number over 100 MILLION times. His current answer is over 41 million digits long! Apparently he and a few others are also working on a distributed computing program for finding larger and larger Lychrel Numbers. It looks like they have in mind a Seti@Home style program with visible results."
does someone want to explain this in layman's terms?
That pretty much sums it up.
His website is a great treasure chest of information for folks looking to do this in their spare time. He seems to be pretty level headed, but just gets off on this.
And people say that putting linux on an xbox is pointless.
Why are we limiting ourselves to base 10?
So why search for these numbers?
Confused...I am...
H&Ks Garf
196+691 = 887 (which is not a palindrome)
Apply the same for 887, 887+788 = 1675 (not a palindrome)
Apparently, you can go on forever like this without ever reaching a palindrome!
152, on the other hand, which I picked randomly, quickly reaches 707 which is a palindrome.
Personally, I don't find this interesting at all. I posted a story a week ago about the prime number problem being solved for the first time with a deterministic algorithm and it was rejected by /. OOPS! Did I just go offtopic? Sorry, mods!!!
All your favorite sites in one place!
I'm rather partial to odd occurences, patterns and facts about numbers and number theory. But I could not find anything on any of the linked pages that could explain why this is interesting. All it seems to be is a variation on: 'well if you take this really convoluted and arbitrary iterating test, every number will work with enough iterations. Except for this one number.' It seems to me that just about any arbitrary iterating test will work for all numbers except for a handful. In order to differentiate the test there must be something unique about it. Are the numbers useful? Do the numbers correspond with numbers found by another test, like every other prime number or something? If not it's just very complicated numerical eeny-meenie-minie-moe.
stipe42
Pick a number, any number. Reverse the digits in the number, add those reversed digits to the original number. Does this sum create a palindrome? If not, repeat the process with the new sum. By example:
87+78 = 165
165+651 = 726
726+627 = 1353
1353+3531 = 4884, a palindrome!
This article is saying that for the thousands of numbers tested, every one except 196 has exhibited this property.
I posted to
What are some real-world applications that this process generates?
Maybe some psuedo-random number generation with the huge strings of numbers that this comes up with?
Any way that this could be used in some sort of encryption?
There HAS to be some useful purpose to this.. There must be, or it wouldn't be the way it is! *twitch, twitch*
-Matt
This guy took time out from washing his hands and counting ceiling tiles to enlighten the world.
Do Lychrel numbers actually have a useful purpose, or is this just a bunch of mathematical masturbation?
I see a number of posts saying "So what?".
Let me explain this in laymen's terms: The geek who spent the past 8 years of his life crunching numbers has definately not gotten laid during that period. This is his day of glory, his existance peaks here.
He can then ride the wave of mathematical fame for about a week - but he can use it to score with the hottest of hotties. Chicks dig brains.
In terms of the actual experiment, the results will allow us to develop a kernel module which can predict how long it will be before you have sex. The more shell logins, complicated bash scripts and mount commands you use, the longer your wait until The Big Day.
So this is good for Linux.
Seems to me their palindrome test is a bit limited, since they only appear to be testing base-10 numbers. What's the use in that? Why not test base-2 or base-16 or whatever? Probably because there is no useful application to this arithmetic curiosity?
So true.
This additional text is purely to avoid the lameless filter. Thank you. Have a nice day.
According to this chart, they've done 40.7 million iterations on 192, but only about 7 million on 887. 887 is the second iteration of 196, so the number of iterations should be the same as 196, but minus one. Apparently they've decided to do the same calculations again, though. And of course, they're doing the same thing with the other iterations of 196. I guess they want to make their pointless calculations as pointless as possible.
Can someone out there explain what, if anything, is the mathematical significance of Lychrel numbers? I understand the basic definition, but I'm not sure what is gained by showing a particular number is or isn't a Lychrel number.
Come test your mettle in the world of Alter Aeon!
Could you use this process for compression? numbers that are palindromes could be expressed as the smallest root number.
thank God the internet isn't a human right.
I found the website to be rather interesting - I remember discussing this in a finite math course many years ago but we spend only like 10 mins on it.
I thought it was great that someone without a lot of math background but a hell of a lot of energy could jump right in and make a difference. I have a great education and background and haven't done as much. I feel ashamed. I gotta start rockin!
It was funny that he doesn't fully understand the math, the programs and still gets things done. He just gets programs that others have created and puts them to use. A math research script kiddie. There should be a website for this. Dump off your interesting math code and people can download and run those that are interesting.
It seems to me that this is the wrong kind of approach to this problem. They would be much better trying to find a generalised proof. You can search as high as you want but you can never prove that the next iteration will not yield a palindromic number otherwise. The difficult part to me seems to be to describe the problem in a simple mathematical form that can be analysed.
were you expecting to see a sig here? perhaps you'd rather see the inside of an ambulance!
Well, I guess this falls into one of those, "I couldn't hurt anything, and if they enjoy doing it, then so what?"
Who knows, maybe someone will think of an application for it. Base two wasn't particularly relevant before binary computers came about, stuff like that.
I've had enough abrasive sigs. Kittens are cute and fuzzy.
This may seem like a trivial and silly waste of time, and it probably is, but the number 196 is interesting. Why? Read this quote:
Whether all numbers eventually become palindromic under this process is unproved, but all numbers less than 10,000 have been tested. Every one becomes a palindrome in a relatively small number of steps (of the 900 3-digit numbers, 90 are palindromes to start with and 735 of the remainder take less than 5 reversals and additions to yield a palindrome). Except, that is, for 196. This number had been carried through 50,000 reversals and additions by P. C. Leyland, yielding a number of more than 26,000 digits without producing a palindrome. Later, P. Anderton continued the process up to 70,928 digits without encountering a palindrome.
ALL numbers up to 10,000 become palindromes very quickly... except for the number 196?
Computer Science is no more about computers than astronomy is about telescopes. --E. W. Dijkstra
I don't care about any (non-existent) practical benefits of doing this, but does finding these Lychrel numbers at least have some mathmatical/scientific purpose?
But that doesn't mean it can't be useful later. A great example of this is the logarithm. Always nice now that it's used in seismology and understanding computer performance, huh? Yet all it was useful for until the 20th century was slide rules.
Karma whorin' since 1999
Star counting nut case, still counting.
Joe Nutcase has been foolowing his quest to count all the stars in the sky, for the past 8 years. We caught up with Joe the other night and here's what he had to say.
"This is totally fucking awesome. I've been counting for 8 years and I still haven't counted them all. It's light totally fucking amazing."
"I'm up to 67.345687 bazzillion and I'm no where near the end. This is so cool. I still get the chills when ever I think about it."
So, what's the point of counting all the stars?
"What's the point? The point is that once I've counted all of them we will know how many there are. I can't begin to explain how earth shattering it will be to.... Shit!!! You made me lose my place! Now I've gotta start all over again!"
Uhm, yea. We'll talk to you later Joe.
but the lameness filter blocked me. Dammit!
sulli
RTFJ.
I don't think this is a mathematical problem... reversing the digits in a number isn't a mathematical procedure, is it? I don't think there is a mathematical relationship between one particular number and another which has the same digits in reverse. Why should there be? That's like thinking that spelling a word backwards will give you a word with the opposite meaning. I think this situation is just a coincidence, and the only meaning is related to the appearance of the numerals themselves rather than any property of palindromic numbers.
Why revolve around base10? Just use base16 or base2 or base7. Of course the rules for finding the numbers is pretty simple and really obvious when you attempt to do it with base2 numbers.
Number theory always ends up being useful, sometimes much to the chagrin of the number theorests. In fact, mathematicians sometimes take pride in working in fields that they imagine are completely without application in the real world... ... until an application is found, and it almost always is, eventually.
"No one shall expel us from the paradise that Cantor has created for us."
- David Hilbert
The number 196 NEVER becomes a palindrome, no matter how many iterations you do. I have assuredly found an admirable proof of this, but the Post Comment box is too narrow to contain it.
(Apologies to Fermat.)
I don't buy a computer based on adds, I go to hardware sites and look at benchmarks and read reviews. People who are too lazy to do this deserve to get ripped off. I don't expect companies to be honest about the quality of their product in any industry and no one else should. I will say this though, if this law suit is won by the customers, I'll be suing Cheer for misleading me into buying their product when I later find out that Tide is clearly better.
trivial deterministic algorithms have of course been available, but not fast ones
This seems like an absurdly irrelevant number study, but it is intriguing from a purely number theory perspective.
In any case, what is the mathematical function for inverting the digits of a decimal value? (i.e. 192 -> 291). I'm not including textual "move the digits around". I hardly am concerned with number theory anymore, but this does intrigue me.
No I just have to go count the tiles...
this is so f'in stupid.
I think that my "extra" CPU cycles would be much better put toward distributed AIDS or cancer research. SETI seems somewhat of a waste of time, pedantic stuff like this even more.
-- You are in a maze of little, twisty passages, all different... --
Thank goodness it's not the number 42...I'd be on my way to the local pub, towel in hand, if it was!
This is not a dream, not a dream...we are transmitting from the year 1-9-9-9.
This site doesn't seem to be much. He seems to have found that the numbers will generally come to make a palindrome over time. This is something cute but nowhere on the site does he even try to explain relevance to anything. In addition, this guy doesn't seem to know much of anything with math. He considers infiniti a number, he is suprised by obvious things, etc. He reminds me of the Greek philosophers before science as we know it came to be. He thinks whether something makes sense rather than taking it step by step in a proof (or for the simplicity of explaining it, a pseudoproof).
Of all the hairbrained distributed computing projects. I mean... with RC5 there was a point, a competition and a demonstration of the strength of the cryptography. With Seti there's real science behind it, looking for what would be the greatest discovery in the history of the human race (that we're not alone). But just finding some highest number of some arbitrary hoop-jumping number nonsense? Jesus Christ is there really nothing more productive these people could be doing?!
We all know why 196 won't become a palindrome! The man doesn't want it to. The man taught you the math, and he showed you the number. This keeps you busy counting, adding, iterating, while the man laughs!
All these numbers belong to the man. It's true, and everyone knows it. The man controls the math, and he controls you.
When you buy a new PC tower from the man you know the only thing it will ever be good for is comig back at midnight and throwing it through his window. The man sells you motherboards with manuals that don't have jumper settings, CPUs that don't have information on core voltage and frequency, yeah the man rules your world.
I tried to get it my way at Burger King, but the man wouldn't let me. Police man, army man,
manager, they all rule you. You can add numbers till you die, and the man runs your funeral. The man owns your number, all your numbers. Phone numbers, SS numbers, ID numbers. The man controls the numbers.
The man says I'm offtopic, and he calls me a troll. The man runs my ISP and the message boards.
The man is on IRC ruling your chat with an iron alloy fist. Still you add numbers, the numbers that he gave you. The man rules your world!
The result for 196, if that really is a seed for an infinite palindrome series, applies only for base ten. 196+691=887, 887+788=1675 but 1675 is binary 11010001011, a nice binary palindrome.
There is, of course, nothing special about base ten mathematically. We people just commonly use it.
The number 196 happens to be the first of them. How about 158? 158 + 851 = 1009, which isn't a palindrome.
matula
Actually the numbers can be very useful when creating encryption algorithms.
This is a classic example of what I call the fallacy of numerology, which is projecting arbitrary features of a representation onto that which it represents. (It is a mistake in the case where the symbol represents what it does in virtue of an arbitrary association between them, by convention or whatever. There might be representation where the symbol represents what it does in virtue of resembling that thing, e.g. a picture of a circle.) Numerals and numbers are the perfect example. There is no interesting properties of numbers at issue here, only of the language of arithmetic.
how do you paralellize iterating a function? I just doesn't make sense on that level...
care to elaborate? That sounds interesting.
stipe42
They never said you couldn't start with a palindrome
879, 1997, and 7059 also have this property, whatever it is. The guy even explains this on his site. I wonder who he is, and why he doesn't put his name anywhere.
What IS a palindrome? I saw that it is something with the same number? Can someone please make it clear to me? Thanks.
If anyone has some time to waste, it'd be fun to create a fractal drawing of it. Well it's not really a fractal, since it's integer, but anyway. It'd be only a single line of pixels (or a symmetric 2d reflection), and the color code represents how many iterations it took to reach a palindrome. I'm guessing it may not look real spectacular, but who knows...
DZM
Excuse me for possible retardation, but surely distributed Lychrel number algorithms *cant* exist? The equation is recursive and therefore each calculation requires the knowledge of the number before it... And so, only one thread even can be used to process this with one instruction (add).
It gets to be more questionable when they talk about a "SETI@Home" type of distributed application : For something so thoroughly useless, that is nothing more than an absurd waste of electricity (and it is a waste of electricity: Computers are left on when they would have been turned off, and barring that the CPU is actively consuming power rather than the dramatically lower power usage halt instruction which it would be running normally).
Did he ever bother to check if they're the palindromic result of a smaller non-Lychrel number?
The beauty of the process is the computer does all the math (Y'see back before Quake was invented, computers were sometimes used for *computing*. Slick, huh?). The human just stops in and checks up on it once in a while. Simple, effective.
I'm almost sure the answer to all of this has to do with Nature's Harmonious Time Cube.
My deviantArt site
Now, I'm not any kind of mathematecist, but it seems to me that when you start reversing numbers like this (which is not a mathematical operation), aren't you just creating artifacts of the base of the numerical system?
What I'm asking here is, if I take 196 and convert it into, say, binary or hexadecimal, will it still exhibit these properties?
So the iteration, when seeded with 196 or whatever, can run endlessly without becoming a palindrome (in base 10)...and this is the only one found under 10,000. Isn't that because after 10,000, the numbers are just too large to realistically luck out like that? After all the iteration practically doubles every time. That would get your needle in a haystack quick enough. Are we supposed to be helping or hurting the terrorists with this?
Yeah, that is a little more questionable when you start talking about opportunity cost, but when you get down to the basics, there are a lot of useless pursuits that waste resources but make people happy in some way.
Car audio springs to mind. Think of all the gasoline wasted by burning an extra 500 watts all the time. Unless you are going to go facist on people and tell them they can't waste their time and money with things that don't really benefit society, then you really can't say much about something like this.
I've had enough abrasive sigs. Kittens are cute and fuzzy.
(196) 11000100 + 00100011 = 11100111
But, perhaps expounding in my own way the thoughts of the previous anonymous poster, there is always utility in adding to the toolbox of mathematics. For instance, strong encryption schemes can be created by chaining rounds of substitutions and transpositions. You could view the creation of these numeric palindromes as a simple, degenerate case of that process. (Or at least you can make the case that there exists similarities.) And, the mathetmatical process that creates the redundancy of palindromes (and redundancy is bad for encryption) is colvoluted and hard to understand.
Long story short, if mathematical theories and tools are created to explain just why, say, the number 196 is special given these mathematically strange operations, then those theories may actually be very broadly applicable in both encryption and number theory in general.
... or something like that.
A lot of people here are dumping on this as irrelevant. Just wait until the next Einstein or Hawking or Weird Al figures out how to use 196 to fold space and make instanteous cross-galaxy travel possible. Or better yet, turn all of MS into a family-run flower shop. Then we'll see who's laughing.
This is not pure mathematics, as it relies on the numbers being represented in a certain base.
Number theory per se is considered part of pure mathematics, the N in NIGGERS. When my number theory book defined some basic concepts in terms of first principles, it defined "base" soon after it defined "multiplication". It roughly went like this: The base b representation of the positive integer n is a finite sequence of non-negative integers less than b such that the last element x > 0 and the sum[i = 0..n-1](x[i]*b^i) = n.
This statement about 196 and base 10 is a statement about sequences of numbers.
Will I retire or break 10K?
I have assuredly found an admirable proof of this, but the Post Comment box is too narrow to contain it.
I suspect that you're either bluffing or just making a bad joke analogous to the DMCA jokes, the Beowulf jokes, the "All Your Base" jokes, the "2. ???; 3. PROFIT!" jokes, the "Priceless" jokes, etc. that get moderated to -1 on Slashdot.
On the other hand, if you really do have a proof or disproof of the existence of Lychrel numbers, then fire up Emacs, make a web page outlining your proof, and post it on a public server. Go to GeoShitties if you have to. Leave the finest details to the reader if you have to. Pure mathematicians want to see it. Bad.
Will I retire or break 10K?
This effort is interesting for its hack value, but it seems to me that 196 isn't special so much as a "Lychrel" Number but as an input to the formula. That is, a prime number clearly has a unique and specific mathematical property, but 196 is just .. 196.
... the length of any substring of the resulting digits that are numerically ascending or adjacently equivalent is a prime number. Bonus points if there is more than once sequence in the result that is a prime number.
I propose a different formula. Take a number, multiply it by the reverse of itself (instead of adding it) and then, oh, subtract the original number plus its reverse, and repeat until you have, hmm
This is a made-up-while-typing-in-the-slashdot-comment-box problem, yet you could have whole web sites dedicated to the search for these 'special' numbers. But are they really 'special' numbers?
BTW, I searched the site and Google but didn't find any indication of *why* the name Lychrel was chosen, only the blackboard entry where they were first named.
It is indeed an arbitrary definition of palindrome. Try doing this in binary:
196 (Dec) = 1100100 (Bin)
1100100 + 0010011 = 1110111
However, there may be different sets of Lychrel numbers in different bases. (I don't know, this is the first time I've heard of Lychrel numbers.)
"Screw causalilty!" -- Prof. Farnsworth
Well, I guess this falls into one of those, "I couldn't hurt anything, and if they enjoy doing it, then so what?"
Ahhh... the "perverts" excuse!
Is the set of all palindromic numbers of the same 'size' as all natural numbers?
Actually, slide rules were extremely important in the old days...
While commerce has used mechanical calculators for a long time, there were no widely available equivalents for engineering calculations, AFAIK.
So, pretty much everything done in the 19th century and after, until about 1950, was designed with slide rules.
I myself had one -- it was a fascinating instrument. BTW, it's easy to build one...
As the primary author of the distributed Lychrel search, I would like to point out a few things (I have paraphrased all "quotes" below based on a perusal of comments so far)...
Does this have any use?
Absolutely none. If you have a use, let us know. Otherwise, it doesn't really have any application. We *have* discovered that iteration of reverse-and-add has fractal nature, does that at least get us a few "coolness" points?
This won't work, the algorithm has too much serial dependancy.
Wrong on two counts. First, the core concept of reverse-and-add *does* yield to parallel implementation (Jason Doucette worked through this one, and has come up with a *really* elegant solution). Second, searching for Lychrels does not involve "deep" iteration of reverse-and-add. It only requires taking a *lot* of numbers to a certain arbitrary depth (10000 digits more than suffices at the starting value range we currently can deal with). So, although deep iteration takes some work to efficiently parallelize, Lychrel searching gives a nearly linear speedup with the CPU count.
Why limit yourselves to base-10?
For the simple answer, all lower bases have trivial proofs of either an infinite number of non-terminating sequences, or no known non-terminating sequences. This makes base-10 the lowest "interesting" base to work in. Of course, the question strikes me as odd... Why not ask why we use base 10 for counting? Why not base 2, or 7, or 60? Just as meaningful of a question.
What does "Lychrel" Mean?
196 exists as the lowest (base-10) number that does not seem to terminate on iteration of reverse-and-add, but not the only one. Obviously, any consequent of 196 (such as 887) will also never terminate. Other numbers also never terminate, such as 879, and they never converge with the series generated by earlier numbers either. So, needing a name for these numbers, Wade VanLandingham picked the word "Lychrel" (pronounced la-shrel), and the active 196 community accepted it into common use.
And, the big question...
Can I run your distributed client?
Yes and no. First of all, it will take me about another 3 weeks of development to finish the client (the server program already works adequately, for now). Second, our currently available server machine can only handle around 100 clients, and just within the 196 community we have offers to run about half of those already.
So, although we will gladly consider offers to run the client, as our single biggest need for help we require a nice server with a fat pipe. The actual bandwidth needed won't go that high, but the total could (our next data set, 1E10, we predict will take 20-40MB of traffic. The 1E11 set will take up to 17 times that, and so on... It grows quickly).
Additionally, most Slashdot readers run Linux. Although I plan to write a Linux client, at the moment my optimized reverse-and-add routine only builds under Windows (mostly because I hate AT&T syntax assembler, I actually prefer coding for Linux otherwise). So, if anyone wants to volunteer to convert a 250+ line inline assembler function (with MMX) from intel format to AT&T, drop me a line (you would of course get full credit for your contribution).
Umm... That seems to cover most questions.
http://www.mathpages.com/home/kmath312.htm
"player 4 hit player 1 with 0 stroms"
Of course this is only relevant depending on base ten numbers. You milage will vary depending on the base.
It is a quirk of numbers based on the nuances of the notation system you are using, and as such is amusing for some.
I imagine there may be more palidromes in a base two system, vs, say, a base 666 system. (to choose an arbitrary base).
Oddities of this sort of thing might have some usefulness in offbeat cryto systems, but beuyond that ...
"It is a greater offense to steal men's labor, than their clothes"
Binary computers actually arrived on the scene over 200 years after Boolean algebra was invented and refined by George Boole and first presented in a paper by him in 1854.
"Boole's system of logic is but one of many proofs of genius and patience combined." was how De Morgan commented. It is not recorded how many whiny teens said "so what".
It's first real practical use was for telephone switching.
There are places where the networks are not touching,and there are places where they are-Boeing's Lori Gunter
http://www.jasondoucette.com/worldrecords.html
Under procedure you'll find this. I'd like to see a mathematical proof or the work Mr. Doucette did to make the assumption bolded above. Mr. Peters only showed that up to around 500,000 iterations the current lychrel numbers (under 9,999,999) haven't shown a palindrome, nothing more.
Generalizing based on a small set of numbers is not prudent. Since this problem does not seem to have any practical application, I would hope people would come up with mathematical proofs and maybe, as some others have already suggested it, generalize the proof to include numbers other than decimals (binary.. etc), numbers with different base.
Basing work on shaky grounds, no matter how brilliant the derivative work, has little value. For the most part, this problem is a numerical curiosity. He seems to be the first person to take an interest in this problem, trying to solve it utilizing computers and had the ability to optimize the algorithm by making certain assumptions.
It would have been more interesting and amazing if he had shown mathematically that there are no lychrel numbers, that all numbers taken to enough iterations will result in a palindrome.
If it turns out Mr. Doucette was right about these lychrel numbers, then he just got lucky and turned out that the nature of the numbers happened to coincide with his observations and assumptions.
Say Mr. Doucette rolled a dice, not knowing what the numbers on the dice are, and he got the number 1 five hundred times in a row and made the assumption that the chance of a different number on the dice is slim and he ignored that possibility. Surely people can see the flaw in that. He may be right, but it is not a prudent way to search for lychrel numbers.
There is a very nice account of one famous
r ee years.html
computer geek's battle with this number.
http://www.fourmilab.ch/documents/threeyears/th
The account reminds me that computers are more
for just word processing and surfing the web. We
can explore interesting and amusing phenomenon
with them. I wish I weren't so jaded.
Would this, actually? If so, it's a shame. That's an obvious case for tail-recursion elimination. I guess perl doesn't demand this like scheme does?
Will parrot support the ability to do stack-based tail recursion elimination? I know that this has been one of the big pains of java-based scheme implementations: For security reasons, it's hard to mess with the stack in the apppropriate ways. Right? Cause that code needs only constant stack space, right?
It'd be a shame if this new technology everyone is investing so much in... OK, I meant parrot, that apparetnly perl 6 will be based on... Is not going to have hooks to support that type of optimization that doens't just improve coefficients, but takes you from O(n) to O(1)...
I'm not familiar with this problem, so what I'm going to say is probably well known to students in the field.
It seems like the best way to produce a palindrome on the next step is for the sum of the kth digit and the kth-from-the-end digit to be less than 10. Then there will be no carries and we get a nice palindrome.
For random numbers, the chance of this being true is 1/2 for each digit in the first half of the number. Therefore with a number of length 2n digits, the chance that it will be palindromic on the next step is 1 in 2^n. (That' s one in two-to-the-nth power.)
If a number is not a palindrome on one step, it will become about one digit longer from the reverse-and-add. So at each step that it is not palindromic, the chance that it ever will become palindromic decreases.
From this perspective, it's not surprising that most small numbers become palindromes after a few steps, but that as we get to larger numbers we will find more and more that seem to never become palindromic. After some length the chance of ever again getting a palindrome is so remote that there is no point in continuing - your computer is more likely to make a mistake than for the number to happen to have the special form that can create a palindrome.
196 just happens to be a number which "gets lucky", it escapes out of the small-number region where most form palindromes. Once you get past a dozen or so steps you'll probably never get a palindrome.
There doesn't have to be anything special about 196, it's all a matter of chance and odds.
That's how I see it, anyway.
While I've been wating for the film to start I came up with this....
:/.
:-)
The only problem is doesn't work when the numbers are _really_ large (like hundreds of characters long), I think that's an issue with one of the functions
#!/usr/bin/perl
# Stupid Perl script to find Lychrel numbers.
# Yeah yeah inefficent, but very quick and easy to write
# Iain Collins, iain_collins@mac.com
use Math::BigInt;
use Strict;
my $start_number = $ARGV[0];
print "Searching For Lychrel Number, starting at: $start_number....\n";
my $forward_number = $start_number;
my $reversed_number = reverse($forward_number);
my $result;
my $result_tmp;
my $i = 0;
my $count = 0;
while ($i == 0) {
my $n = Math::BigInt->new($forward_number);
$count++;
$result = $n->badd($reversed_number);
$result =~ s/\+//g;
$forward_number =~ s/\+//g;
$reversed_number =~ s/\+//g;
print "$count: $forward_number + $reversed_number = $result\n";
$result_tmp = reverse($result);
if ($result_tmp == $result) {
print "Palendrome Found?\n";
$i++;
}
$forward_number = $result;
$reversed_number = reverse($forward_number);
}
In a nutshell, you start with a composite number, write down the prime factors in decimal in ascending order of size and so get a new number, which may either be prime or composite. If prime, then this is the Home Prime of the number you started with. If composite, repeat.
All the numbers below 100 reach their Home Primes rather quickly - except for 49 (and thus, 77). This one is expanded to 95 steps by now and has grown into a 194 digit number which is becoming increasingly difficult to factor. The last 15 steps of this sequence were done by Paul Leyland of Microsoft Research, Cambridge, and myself. The 95th step is factored down to a 153 digit composite which we are struggling with right now. See Patrick De Geest's page for the current status of this problem.
A difference between Home Primes and the 196 problem is that Home Primes can be shown to exist for every number - the probability that no Home Prime is found in as the number of expansion steps goes to infinity converges to zero. It is, however, quite possible that the number gets too large to factor with today's resources before the Home Prime is found. (That seems to be happening in the 49 case right now.) AFAIK no guarantee of a terminating sequence exists for the Palindrome problem, it is possible (and likely) that the 196 sequence spins off into infinity without ever becoming palindromic.
As far as I can tell, there is no practical use for either Palindromic numbers of Home Primes. It's just recreational - a way to spend spare time no better or worse than board games or sports on the TV. Except it involves massive amounts of cpu time and pretty advanced algorithms (i.e. ECM and GNFS) - the study of which I find extremely intriguing. It's probably one of the geekiest ways to spent your time (not that I were proud of that, I merely can't help it).
Alex
Heisenberg may have been here
Might yield an interesting fractal landscape.
Okay, so it's late and I was tired... but the first thing I tried when I reached for a calculator was reversing 196 (=691) and adding the sum of the digits (1+9+6). Adding them both together gives 707 (a palindrome).
Spooky or what?
But seriously, could this have anything to do with why it may have this odd property?
Of couse, was using "==" to check for matches (Perl wiggs out at this). Testing for matches by treating the values as a string works fine. (i.e. by using "eq" instead of "==").
:-)
This versions works, even with ReallyBigNumbers...
#!/usr/bin/perl
# Stupid Perl script to find Lychrel numbers.
# Yeah yeah inefficent, but very quick and easy to write
# Iain Collins, iain_collins@mac.com
use Math::BigInt;
use Strict;
my $start_number = $ARGV[0];
print "Searching For Lychrel Number, starting at: $start_number....\n";
my $forward_number = $start_number;
my $reversed_number = reverse($forward_number);
my $result;
my $result_tmp;
my $i = 0;
my $count = 0;
while ($i == 0) {
my $n = Math::BigInt->new($forward_number);
$count++;
$result = $n->badd($reversed_number);
$result =~ s/\+//g;
$forward_number =~ s/\+//g;
$reversed_number =~ s/\+//g;
print "$count: $forward_number + $reversed_number = $result\n";
$result_tmp = reverse($result);
if ($result_tmp eq $result) {
print "Palendrome Found?\n";
$i++;
}
$forward_number = $result;
$reversed_number = reverse($forward_number);
}
.... erm ... yeah... but why? Do they expect to find a message from God... or?
If Google really cared they would fix Android Chrome to reflow text, instead of discriminating
...is actually 196!
Damn! I've been worshipping the wrong number all this time!
If Google really cared they would fix Android Chrome to reflow text, instead of discriminating
the sources
we discovered a new way to think.
I dont.
As you've pointed out, every palindromic natural is a natural therefore set of all palindromic naturals is smaller or equal in size to the set of all naturals.
For any natural, reverse its digits and concatenate into a palindromic natural. This doesn't give you every palindromic natural, but it shows that the set of all palindromic naturals is larger or equal in size to the set of naturals.
Thus, the set of palindromic naturals is either smaller or equal in size to the set of all naturals and it's either larger or equal in size to the set of all naturals. It follows that it's equal in size.
Please.
Yeah, I'm sure 196 is meaningful in base 10. And maybe something else is meaningful in base 14 or whatever. Unless god works in decimal I don't see much significance in this other than interesting artefact of our number system. Still, if someone could create a proof...
In order for addition of a digits-reversed number to yield a palindrome, there must be no carries in the addition and hence each pair of digits must sum to 9 or less.
This is an assertion from John Walker's Three Years Of Computing . Several other sites reference this statement and it appears to be over generalized. Certainly for any addition of this form the sum is a palindrome but not all digit-reversed sums that are palindromes are of this form. For example conside
74 + 47 = 121
or
7744 + 4477 =12221
These are only a few counter examples. There may be some general rule on how to generate all such numbers.
I hope this statement isn't fundemental in any greater works.
Being the insane geek I am, I quickly whipped up a Perl script that I *think* works. I tested it with an example given (87), and got 4884, which is correct.
The program will print out the number of time's it's looped (the number of numbers it's tried), and then what the number is. Every million numbers (I wanted it to be big enough that it wasn't printing out miles of crap, but small enough that I got occasional outputs to know what it was up to), it prints out the time elapsed, the number of repititions, and the current number.
#!/usr/bin/perl
$in = $ARGV[0];
for ($x = 1; $x <= $in; $x++) {
$reverse = reverse($in);
$in = ($in + $reverse);
$back = reverse($in);
if ($in == $back) {
print "$x\t$in\n";
exit;
}
if ($x % 1_000_000 == 0) {
$time = (time - $^T);
print "\tat $x... $time sec elapsed... $in\n";
}
}
# the end...
Constructive criticism and whatnot is welcomed. (And yes, I know, my variable names suck...)
________________________________________________
suwain_2
thanks. that was simple enough.
It's a great book. It will turn you on to math, even if you aren't in to math.
I couldn't believe how exciting the author made this topic. I stayed up late as if I was reading tom clancy.
freakin good book. and funny joke too, to the Parent.
What's so special about base 10, other than that most of us have 10 digits on our hands? (Devil's advocate)
Numbers patterns become interesting when they can be mapped to real-world phenomena where the phenomena closely "follow" the patterns.
Has anyone tried to find "Lychrel Numbers" on other bases?
-gps
This webpage has some of the longest delayed palindromes ever found. It's fun reading, too. This guy has programmed a lot of interesting stuff in his CS "career" so far ;)
http://www.jasondoucette.com/worldrecords.html
--- Eat my sig.
Fuck off loser.
It is not recorded how many whiny teens said "so what".
:)
Haha, now with the modern marvel of Slashdot, the "so what" score of any new idea can be qutified and archived for history.
"Slashdot's system of comments is but one of many proofs of ignorance and impatience combined."
I've had enough abrasive sigs. Kittens are cute and fuzzy.
Seems to me any proof would start here.
What does it mean mathematically to reverse a number?
in some cases you make the new number larger
(24 becomes 42)
some cases you make it smaller
(42 becomes 24)
some cases nothing happens
(44 becomes 44)....THESE cases are palindromes themselves.
interestingly enough, adding two palindromes doesn't always make another palindrome
44+44=88. 101+101=202 7337+7337=14674
but the algorithm stops here anyway.
You can easily classify those which get larger upon reversal by checking to see if the last digit is larger than the first.
Same for those that get smaller.
Then some numbers have an even amount of digits, and some odd. Seems to me there is a balance property involved here. are even numbers more balanced, or odd? I guess odd are, because they'll share the middle digit (a pivot digit).
When adding the reverse, if the number gets smaller upon reversal, the resulting sum is closer to it's own value...not sure if that is useful, but I wonder if it's repeated..
i.e. if I take 804 and reverse it I get 408, then I add and I get 1212, closer to 804 than it is to 408. On the other hand, if I start with 408, and reverse it I get 804, and then add I get 1212, which is farther from the number I started with...which really means that all numbers only have to be done for digits ending in values less than or equal to 5.
For example you can solve 400,401,402,403,404,405...and stop...Then when you get into the 800s, solve 800,801,802,803,804,and 805. by solving 804 you solve 408..This can cut down the work. I suppose you can vice-versa this idea, but it's probably better to limit on the ones place than to try to limit the actual size of the number.
ok, so that should shave some time off of our calculating, what about the pivot number.
In this case the number was 0, so that was shared, which means reversing doesn't introduce any change for that place. What if its shared but not zero.
415..514..929 (here the 2 is shared)..oh, wait. we got our palindrome...
wait, maybe it's not 5 in the last place, but rather if the last digit is larger than the current first digit that you skip. or vice versa
anyway, this way you can calculate whether to skip or not, instead of trying to keep track of those you've already found...691=196 in this respect.
weird, if you think about digits 0-1000, 555 is the absolute center of the universe.
We've only got 10 digits (0123456789) and infinite places to put them..
it may be a really really really large number, but it will happen sooner or later.
I seriously doubt that
a) it can't happen eventually
b) anyone can prove that it can't happen eventually
in fact, if you took the 10 digits infinite slots, and algorithm approach you could probably prove that it will happen, but you'd have to prove that it will happen in X number of iterations.
Assuming that there is any significance to such numbers is wasteful. As if the base 10 numbering system is the root of the universe....
well, duh, yes, OBVIOUSLY if N is Lychral so is its reversal R and iteration N+R :p how could anyone slip into thinking (or writing) 196 was the only one less than 10000 ??
I remember reading about this in a magazine from 1984. 'Twas The Transactor, volume 4 issue 6. It includes an implementation for the 6502, though it gives up after 255 digits. And it's less than 196 bytes. Get with the times. ;)
Anyone want source?
202 + 202 = 404 Nuff said.
The plot showing the sequence of iteration-to-palindrome depths for each integer is available here.
The Lychrel numbers (iteration depth>10000) are colored red. Interesting, the maximum non-Lychral depth (number of iterations until palindrome) was 24, which occurs right away at 89 (try it, its a fun one). After that, the depths recur in similarly patterned blocks, with a typical spacing of about ~100 (or occasionally a very close spacing of only 2), and some interesting gaps. The first few Lychrel numbers:
Can you spot the patterns in this sequence? The only thing special I can see about 196 is it is the first Lychral number!
1009 + 9001 = 10010
10010 + 01001 = 11011 Which is a palindrome
----- One piece short of Legoland
...all of its children. After each iteration beginning with 196, you get another number that will never become a palindrome.
196 + 691 = 887
887 + 788 = 1675
Obviously, if 196 doesn't work, then 691 won't, and neither will 887, or 788, or 1675 etc
Or did the article mention that another condition for Lychrel numbers was that the number can't be part of another one's sequence?
PUBLIC SPLIT ON WHETHER BUSH IS A DIVIDER -CNN scrolling banner, 10/15/2004
Then again, how would we know that we've reached the end? They could be very spaced out. What we need is a mathematical proof.
You can't reach the end. Any number whose digits are all less than 5 is obviously palindromic, and the set of such numbers is countably infinite. Thus, the set of palindromic numbers is not smaller than the set of natural numbers.
Since, as you pointed out, the size of the set of palindromic numbers cannot exceed that the set of natural numbers, the sets are of equal size.
the joke you so obviously missed
No, I did not miss the Fermat joke. Note that I accused dave_mcmillen of making a "bad joke". I've just noticed that Fermat jokes in Slashdot pure-math articles are quickly becoming as tired as Beowulf cluster jokes in hardware articles.
Will I retire or break 10K?
Sorry, I wrote this on my windows machine at work, so I don't have a proper sh-bang at the top, but this'll tell you whether or not a number converges to a palindrome in less than 10,000,000 iterations, and if so, where and how. A preliminary run took a long time. :-) Drop the iterations down to about 1,000 and it's pretty quick, and gives you an idea what might be interesting to explore.
;-)
(ps-yes, it was nicely formatted and commented, but the LAMENESS filter rejects code like that.
# Do some perl madness
sub FindPalindrome { my ($value) = @_; for (my $j=1; $j=10000000; $j++) { $value += reverse($value); if ($value==reverse($value)) { print("$_[0] found in $j steps, palindrome of $value.\n"); return $j; } } print("$_[0] might be a Lychrel number!\n"); return $j; } { for (my $i=0; $i1000; $i++) { FindPalindrome($i); } }
Any connection between your reality and mine is purely coincidental.
If you want to link directly to the sequence without using the search box use the following URL:c gi/as/ njas/sequences/eisA.cgi?Anum=023108
:-)
http://www.research.att.com/cgi-bin/access.
My daughter recently covered this at school, but they didn't discuss any exceptions to the rule. However, they chose random 3 digit numbers to check, so there was only a 13/900 chance each child would have a LOT of homework that night
-- Don't believe everything you read, hear or think
Couldn't have said it better myself. I guess a lot of people haven't paid any attention to what Wolfram is trying to say in his new book: this kind of weird algorithmic pattern shit is as common as sand on a beach. Around 1983 people were playing around with wondrous numbers, which at least has the replayability advantage of not producing a monotonic sequence.
My first curse upon the world: this problem has a proof that involves analyzing 100,000 special cases producing 10,000 pages of dense results, and none of these cases can be reduced.
My second curse upon the world: some idiot bothers to find it.
The suggestion that no pure mathematician has any clue about where to begin is not equivalent to saying no pure mathematician has any clue about whether to begin. A proof is hardly worth the paper it gets published on if it doesn't reflect back on other branches of theory.
I, for one, am glad they haven't thrown away that distributed processing power on something trivial like curing cancer instead.
pr0n - keeping monitor glass spotless since 1981.
Before you ask why any endeavor is a waste of time, I suggest you read Arthur C. Clarke's "Nine Billion Names Of God".
hmm we need to add those formulas to gnu pgp makes a nice set of new encryption formulas.....
Encryption keeping governmental power from ging absolute!
Don't Tread on OpenSource
...cuz there may actually be a solution. SETI@Home *has* no solution.
Huh? Maybe you've changed the base on me without telling, but isn't 1854 + 200 == 2054?
Besides, much like this theory, boolean algebra was all but ignored by the mathematical community at large until the 1940s, when the introduction of computers made the field suddenly relevant.
I read the internet for the articles.
hehe those darn century numbers
well I was approximately correct.
my point was that sometimes an idea can arrive ahead of it's time
Mind you, the palindromic properties of numbers will probably have to wait for quite some time.
There are places where the networks are not touching,and there are places where they are-Boeing's Lori Gunter
If 196 will never solve, then it is obvious that 691 will never solve. Also, it is obvious that 295, 394, 493, 592, and again 691 will never solve (what are normally called the 'consequences of 196').
The first iteration after 196, 887, will thus never solve, as well as 788. From these two number, it is obvious that 986, 887, 788, 689 will never solve (the consequences of 887).
The other lychrel sequences under 10,000 are 879, 1997, and 7059. Each of these numbers, and their sequences, and all consequences of these numbers and their sequences will also never solve.
If you are interested in Lychrel numbers, my page here: http://www.jasondoucette.com/worldrecords.html
It shows the numbers that take the longest length of time before they solve. So, they are the closest numbers to Lychrels that aren't Lychrels. It also details my section of the 196 Quest.
Jason Doucette
www.jasondoucette.com
196h+691h=827h; 827h+728h=F4Fh
196=C4h; 691=2B3h
C4h+4Ch=121 or C4h+2BEh=AEAh
I hate all this stupid numer thoery that takes advantage of a particular positional notation system.
The really interesting/imporant numbers to study are those that have no base. Like PI or e.
hummm......... Iwillthinkaloud
if ppl understood more about number theory we would allbe better off. some nessesary genralised definitions need to be understood:
1) how counting and counting protocols work
2) what exactly occurs when rotating about a radix index
3) how geometric series work
4) how the recognised mathmatical proof systems work
in the following i willbe using the modus ponens, i have generalised base.
now the digits in a number couldbe said to be logb(n)
the function of rotation about a radix index can be shewn tobe a division by f(x) logb(r)/(f(x)/n)
this is a fairly simple function! and one that can be seen to be a geometric series with common ratio (f(x)/n), and factor multiple of logb(r)/f(x)
now some ppl in the mathmatical communitie will notice some parallels with two major hypotheses
riemann and ziegler series and fast factoring methods.
so a generalised proof couldbe used for fast factoring i.e. code breaking with an order of magnitude speed increase on current methods.
So why is it on slashdot?
none can proove the method but NSA consider generalised correctness sufficient proof.
So the best we've been able to come up with is that 196 is... weird. But why? Let's analyze it. Hmmm, it appears to be a cubed number. What? No!... It's... It's... 6 cubed or "6... 6... 6... the Lychel of the Beast!" (apologies to Iron Maiden)
I can see that there are plenty of cryptic number patterns that math people seek. But this one seems a bit, well, irrelivant. I can see the need to seek out primes and such but this "new" pattern looks like it was invented for the sake of inventing. I have a super-hard to calculate number sequence I called Slashdom. It is any integer when multiplied by 642867150 results in a number prefectly divisible by the first digit of the result. There I am a genius, now let's devote time and effort into seeking these Slashdoms so we can use them in encryption.
Come on, I tried to find one of the non-palindrom number and my first try succeeded, 3421965. Purely from a math stand point you increase you odds of a non-palidrom number by having this sequence odd-prime-even somewhere in your number.
I find this a novelty, but god help us of some twit gets a noble prize for something related to this.
-=[ Who Is John Galt? ]=-