Catch up on stories from the past week (and beyond) at the Slashdot story archive

 


Forgot your password?
Close
typodupeerror
×
Science

Amateur Quest For Lychrel Numbers 311

Posted by timothy from the martin-gardner-would-be-proud dept.
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."
This discussion has been archived. No new comments can be posted.

Amateur Quest For Lychrel Numbers More

Amateur Quest For Lychrel Numbers

Comments Filter:

  • what? (Score:1, Informative)

    by underworld ( 135618 )
    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.
  • So why search for these numbers?

    Confused...I am...

  • Simple Example (Score:5, Interesting)

    by teetam ( 584150 ) on Sunday August 18, 2002 @01:29PM (#4093283) Homepage
    Consider 196:
    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!!!

    • Re:Simple Example (Score:3, Informative)

      by cperciva ( 102828 )
      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 /.

      You aren't talking about this [slashdot.org] by any chance, are you?
    • Actually what the article says is that all numbers under 5000 or something like that fall into one of 3 'seeds'. for example 196 would be a seed 887.

  • who cares? (Score:2, Insightful)

    by stipe42 ( 305620 )
    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
    • 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.
      • Binary computers actually arrived on the scene over 200 years after Boolean algebra [wikipedia.com] was invented and refined by George Boole [st-and.ac.uk] 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.

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

  • In a nutshell.... (Score:2, Informative)

    by moniker_21 ( 414164 )
    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.

    • Re:In a nutshell.... (Score:5, Funny)

      by Andrew Allan ( 442589 ) on Sunday August 18, 2002 @01:45PM (#4093356) Homepage
      I've found another one!!!

      Try doing it with 691! ;-)
      • I hate you. I spent an hour writing a program to calculate these damn numbers and crunching on 691 before I got the joke :P Oh well, I learnt a bit of GMP in the process, guess it was not all wasted.

    • Re:In a nutshell.... (Score:4, Insightful)

      by tealover ( 187148 ) on Sunday August 18, 2002 @01:55PM (#4093424)
      If you're going to copy stuff, you should at least give credit or show a link to the site that you're stealing from.

      This link [rr.com] comes from a link on the www.p196.org [p196.org] page.

      Moderators: Please mod the parent poster down for dishonesty.

      Thanks.

    • Re:In a nutshell.... (Score:2, Interesting)

      by Uruk ( 4907 )
      Here's simple code to check this property for all numbers from 0 to 100 - adjust to test it for arbitrary numbers: (Do NOT run this on numbers that don't have known palindromes since it will cause a stack overflow. :)

      #!/usr/bin/perl -w
      use strict;

      for(my $x=1; $x < 100; $x++) {
      paltest($x, $x, 0);
      } # End for

      sub paltest {
      my($number, $orig, $reclevel) = @_;

      if($number eq reverse($number)) {
      print "$orig yields a palindrome at recursion level $reclevel.\n";
      return 1;
      } else {
      my $rev = reverse($number);
      return paltest(($rev + $number), $orig, ($reclevel + 1));
      } # End else
      } # End paltest
      • (Do NOT run this on numbers that don't have known palindromes since it will cause a stack overflow. :)

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

    • This article is saying that for the thousands of numbers tested, every one except 196 has exhibited this property.

      Wrong, 196 is though to be the smallest integer with this property. Check the integer sequence [att.com] referenced. It gives 45 integers which are thought to have this property, starting with 196, 295, 394, 493, 592, 689, 691,...

      (I'd bet there are either infinitely many such numbers or none...)

      • Re:In a nutshell.... (Score:3, Insightful)

        by plaa ( 29967 )
        (I'd bet there are either infinitely many such numbers or none...)

        Actually, given a little thought, that's quite trivial to prove:

        Suppose there is an integer N that doesn't become palindrome. Then every integer in its calculation sequence is also an integer that doesn't become palindrome. So either there are no such integers, or there are infinitely many. Duh!

        But the question forms out whether there are infinitely many base numbers: I'd bet that there are either no Lychrel numbers, or there are infinitely many "base" Lychrel numbers.
    • ...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?

  • Real world applications? (Score:4, Interesting)

    by MattC413 ( 248620 ) <MattC413NO@SPAMhotmail.com> on Sunday August 18, 2002 @01:34PM (#4093308)
    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
    • Could you use this process for compression? numbers that are palindromes could be expressed as the smallest root number.
    • (* There HAS to be some useful purpose to this.. There must be, or it wouldn't be the way it is! *)

      What else are unemployed trivia-loving geeks gonna do?
    • 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.
      • Hey man, slide rules helped end WWII. Bombadiers used slide rules to calculate when to drop a M pound bomb from a plane moving at V mph at an altitude Y to hit a target at some distance D in front of the plane. Those aren't simple slide rules, they're often two or three dimensional things custom made for certain types of bombs or aircraft or whatever. Anyway, back when computers took up the entire wing of a building, they didn't have automatic targetting computers in warplanes.

        Anyway, ordinary slide rules were commonly used by engineers up until pocket calculators became available (which I guess would be the 1960's or so...). It is the only way to quickly multiply large numbers by hand (unless you're Rainman and can do it in your head).

        In case you don't know, logarithms are rather simple.

        Say you want to find A*B, where A and B are rather large numbers and you don't want to multiply them by hand. log(A*B) = log(A) + log(B), a useful property. So find log(A) and log(B) using your slide rule. Add them. Then do the inverse log. That's A*B. Multiplying by using addition and tables of logarithms. Fun stuff, huh?

        And yes, it works with any "base" for the logarithm, base e (the "natural" log), base 2, base 10, whatever.

      • Yet all it was useful for until the 20th century was slide rules.

        ?????

        You're heart's in the right place but your facts are way wrong on this one. Logarithms were developed for the purpose of changing a then-hard problem (multiplication) into an easy one (addition). They were useful for centuries before the 20th. Read any standard text on the history of mathematics.
    • OK, I just read about these numbers for the first time just now, but I'd guess that there isn't a lot of significance to them. I mean, if you're looking at the digits, then it becomes relevant that you're using base-10. Usually in these sorts of cases, you only find important stuff in dealing with base-2. But then again, this is just my ever-so-slightly educated guess. If anyone really does know how these numbers may be significant, I'd like to hear it!

    • I don't understand why this is interesting at all. These properties only matter for numbers expressed in base 10 (I mean, for other bases other numbers might exhibit the property, but the property is inherent to a standard base expression of the number).

      A particular base expression of a number is not the number, it's a representation of the number. There are plenty of ways to express a number that don't involve any base, much less base 10. To me, interesting mathematical properties are independent of the expression of the number, like primality, arithmetic properties, whether it's algebraic or trancendental, etc.

      The notion of 'palindrome' doesn't apply to numbers at all. It may apply to your representation of the number, but I can come up with a representation that is or is not a palindrome for any number you like. I just don't get the interest.
      • You know, I sensed some bogosity here, but I couldnt' quite tell what it was. I think you've put your finger on it. Are there any interesting number-theoretical properties that depend on what base you express the number in?
      • People seem to have a very hard time seporating numbers from their representations. I used to teach a course on computer representation (int, float, machine language). I used to start one lecture by writing the numeral five on the board and explaining it wasn't five. Just a representation of five. Maybe I should have started with "cat". People don't that the letters C-A-T aren't a cat.

        It took most people a while to understand (long office hours). Some people never understood the difference. They got really lost when I got to 1's and 2's complement.

        The title of the article states that it's an amateur search. I can't see why a professional would bother. It's entirely unique to beings with 10 fingers and doesn't exsist in Plato's world of numbers.

        Kind of like when the date and time was 20/02/2002 20:02. It's kind of cool, but just an artifact of how Americas represent dates and times.

  • Arbitrary definition of a palindrome? (Score:4, Insightful)

    by PseudoThink ( 576121 ) on Sunday August 18, 2002 @01:37PM (#4093323)
    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?
    • Yes I thought of that. Sort of like being "English Centric". Regardless of base if there is only one number that doesn't obey this rule then that is interesting. I'm not sure what for but interesting.

      A solution waiting for the problem.
    • Not just the test. The digits reversing part is also based on base-10. Could be interesting to mix the bases for the test and the reversing.

      As for the use of base-10 rather than another base... probably because we have 10 fingers? :P
    • Since when does pure mathematics need to have an obvious application? Some people study math just because it's interesting. Sometimes, people come up with areas of number theory that don't immediately look promising, but that later get developed into something very useful, like optimum golomb rulers, or the mathematics that goes into public key crypto.

      To get into the mind of a mathematician, you must understand the cardinal rule of math - that there is no such thing as an uninteresting number. All numbers have interesting aspects about them (strange prime factorizations, that they're palindromes, that they're the smallest sum of three consecutive cubes, whatever) but here's the real kicker - there's no such thing as an uninteresting number because if anybody was to ever find an unintereting number that had absolutely nothing special about it, it would be interesting purely for the reason that it doesn't have anything interesting about that.

      Grasp that, and you can grasp why people do things like this. It's an intellectual exercise that some happen to like quite a bit.

    • Try base 196. It works in that: 10 + 01 = 11! Wow!

      You can do that to every number in at least one base. What definitely would be interesting is to find some number it only works for in its own base. Or to find some special properties of numbers that are defined by what bases it works in, how many steps it takes in each base...

      In any case - and I'm sure you've heard this a lot - it doesn't matter that there's no apparent useful application. Stop being so practical.
    • Check the sites on this. There are generalizations of the phenomenon to arbitrary bases

      http://www.mathpages.com/home/kmath312.htm [mathpages.com]

  • Why? (Score:1)

    by SagSaw ( 219314 )
    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.
  • 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.

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

  • All the apathy here... (Score:2, Interesting)

    by Sivar ( 316343 )


    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?

    • Re:All the apathy here... (Score:4, Insightful)

      by pomakis ( 323200 ) <pomakis@pobox.com> on Sunday August 18, 2002 @02:03PM (#4093464) Homepage
      What would be interesting is coming up with a proof of why 196 exhibits this peculiar property. Until then, it's actually impossible to prove that a number is a Lychrel number. In fact, it's impossible to prove that there are any Lychrel numbers. Whose to say that the 20 billionth iteration of 196 isn't going to result in a palindrome?

      Until and unless there's a proof of why Lychrel numbers exist, the whole concept is quite uninteresting beyond a passing "neat".

      • It's obvious to me anyway, on an intuitive level, that if an iteration goes beyond a few digits in size, the likelyhood of it palindroming plummets. I bet number of non-Lychrels that require 50+ iterations is unbelievably low, or even zero.

        Of course, I too wonder what in the hell this is good for.
      • Given a 2*n digit number, it suffices to generate a palindrome if the sum of the i-th and (2n-i+1)-th digit is less than 10 for all i between 1 and n. It follows that at least (2n)/(2^n) numbers of length 2*n will immediately form palindromes. While less obvious, it is also true that if the sum of the i-th and (2n-i+1)-th digit is greater than 10 then the next iteration can only generate a palindrome if the sum of every digit and it's counterpart is greater than 10 (e.g. 9292 -> 12221). Not all numbers with this property will immediately form palindromes (e.g. 9393 -> 13332), but it is a requirement. This property holds for an additional (2n)/(2^n) numbers.

        Hence the probability that a number of length 2*n will immediately form a palidrome is 1/(2^(n-1)) for each iteration.

        On average, the number gains 0.5 digits per iteration of the algorithm. Consequently for a number with 2*n digits, after infinite iterations, you expect to have encountered a number of palindromes approximately equal to Sum(1/2^(n-1+k/2)), k=0 to infinity => ~6.8*2^(-n).

        A straight forward density argument shows that there have to be some Lychrel numbers and that most numbers with a large number of digits are Lychrel numbers, but of course it doesn't tell you which particular numbers have this property.

        Obviously I haven't been entirely rigorous, but afterall this is slashdot.
    • 196 _can't_ be the only number < 10,000 with this property of never generating a palindrome. In fact, 887, 1675, and 7436 must also have this property:

      196 + 691 = 887
      887 + 788 = 1675
      1675 + 5761 = 7436

      Clearly, if any of 887, 1675, or 7436 eventually lead to a palindrome, then so will 196. So why do people just keep talking about the special 196? It might be the first, but certainly not the only one < 10,000.

      • Yes, that's a good point. I believe whats special is that 196 is the start of this chain, and only numbers this is true for are the ones in this chain. The question is: do they have a special property, or is it just some kind of base 10 fluke?

      • That's true. I need to stop posting right after I get up. :)
      • I was interested in the magic of the number 196, so I computed the "palindrome yield" for all numbers up to 3000. I defined as a "Lychrel number" any for which no palindromic sum was found after 1000 iterations. Remember that the probability for a subsequent number in the series to yield a palindrome when summed with its reverse is .45^(n) where n is the number of digits in that number. At a depth of 1000, n~400, and the probability is ~1e-140!!! Of course, it's not really random, for why else could the number 89 succeed with a palindrome of length 13 (probabilitly 3e-5). However, as you'll see, we could have chosen a cutoff of 100 or even 30.

        The plot showing the sequence of iteration-to-palindrome depths for each integer is available here [arizona.edu].

        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:
        196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986, 1495, 1497, 1585, 1587, 1675, 1677, 1765, 1767, 1855, 1857, 1945, 1947, 1997, 2494, 2496, 2584, 2586, 2674, 2676, 2764, 2766, 2854, 2856, 2944, 2946, 2996

        Can you spot the patterns in this sequence? The only thing special I can see about 196 is it is the first Lychral number!

    • Re:All the apathy here... (Score:5, Insightful)

      by ddstreet ( 49825 ) <{ddstreet} {at} {ieee.org}> on Sunday August 18, 2002 @02:13PM (#4093507) Homepage
      ALL numbers up to 10,000 become palindromes very quickly... except for the number 196?

      By definition the numbers 691, 887, 788, 1675, 5761, 7436, and 6347 must also have the same problem, since they're in the chain following 196.
      196 + 691 = 887
      887 + 788 = 1675
      1675 + 5761 = 7436
      7436 + 6347 = 13783

      • Numbers that resolve into the series also have the same characteristic... for example 295 + 592 = 887 394 + 493 = 887 689 + 986 = 1675 Prove it for 196 and all these numbers fall with it.
      • >> By definition the numbers 691, 887, 788, 1675, 5761, 7436, and 6347 must also have the same problem, since they're in the chain following 196.

        Read the article. These numbers don't count exactly because they follow in that chain. Only the seed of a chain counts.

    • It's not true, though. (Score:3, Informative)

      by dark-nl ( 568618 )
      879, 1997, and 7059 also have this property, whatever it is. The guy even explains this [rr.com] on his site. I wonder who he is, and why he doesn't put his name anywhere.
      • 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);
        }

        • 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);
          }

  • Proof for 196 (Score:3, Funny)

    by dave_mcmillen ( 250780 ) on Sunday August 18, 2002 @01:55PM (#4093418)
    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.)

  • Cpu Cycles (Score:2, Insightful)

    by Mister Transistor ( 259842 )
    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.
  • 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
  • Did he ever bother to check if they're the palindromic result of a smaller non-Lychrel number?
  • Is the set of all palindromic numbers of the same 'size' as all natural numbers?
    • So you want to know if there is an infinite number of palindromic numbers? Probably.

      There can't be more palindromic numbers than natural numbers since each palindromic number is a natural number. And since we measure infinities by putting sequences in correspondence with the natural numbers, the size of the set of palindromic numbers cannot exceed the size of the set of natural numbers. Consult W. Rudin's "Real Analysis" for a good proof of this.

      If there is only a finite number of palindromic numbers than a computer could exhaustively search and enumerate all of them. 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.

      However, number theory is a very hard nut to crack. The algebraic structure of numbers is quite elusive. Showing how many palindromic numbers there are one way or the other is probably going to be exceedingly difficult. If not because number theory is hard but because there is no practical interest in this subject.

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

  • Three Years Of Computing (Score:3, Interesting)

    by Eharley ( 214725 ) on Sunday August 18, 2002 @04:11PM (#4094014)
    There is a very nice account of one famous
    computer geek's battle with this number.

    http://www.fourmilab.ch/documents/threeyears/thr ee years.html

    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.

  • A little logic (Score:5, Insightful)

    by SiliconEntity ( 448450 ) on Sunday August 18, 2002 @04:27PM (#4094074)
    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.
  • .... erm ... yeah... but why? Do they expect to find a message from God... or?
  • 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 [fourmilab.ch]. 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...)
    • Sorry for the entire comment being fixed-width... I put my code in tags, and that didn't seem to work so well... So I changed the whole thing to code and hit submit. BTW, 12 million repititions in 176 seconds, and nothing found... But I'm beginning to wonder... Answers very quickly get expressed as integers like "1.40025556644157e+15"... Does a reverse() of this return 51+e7...", or does Perl have the "real" number internally? My script doesn't work for long if the former is the case.

      • But I'm beginning to wonder... Answers very quickly get expressed as integers like "1.40025556644157e+15"... Does a reverse() of this return 51+e7...", or does Perl have the "real" number internally? My script doesn't work for long if the former is the case.

        No, Perl does not perform arbitrary precision integer arithmetic.

        Try perl -e 'print scalar reverse (2**60);', for example.

        Also, I don't understand why you're using $x <= $in as the test case for your loop. $in will grow much faster than $x.

        • Ugh... It was kind of written in five minutes, without a whole lot of thought.

          Now that I think of it, I'm not sure what's with
          $x <= $in
          either, but it seems to work for smaller numbers at least. :)

          I hate when I write code, and then later don't understand why something works... Thanks for your comments, though.
  • 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); } }

    • Your program will flag anything as a possible Lychrel number once it gets to the point where Perl represents it in scientific notation, which will always happen in way less than 10,000,000 iterations. In fact, it will always happen in less than 70 iterations. Stick $value in the string printed if it might be a Lychrel number to see what I'm talking about.

      • Quite right. I realized that when I tried to compute 1,000,000 iterations of 196. I had (mistakenly) thought that Perl operated on strings for integers, which would ultimately mean it internally supported BigNums. A minor change to the script to use Math::BigNum and it works fine, though quite a bit slower. :-)
  • I, for one, am glad they haven't thrown away that distributed processing power on something trivial like curing cancer instead.

Slashdot Top Deals

I judge a religion as being good or bad based on whether its adherents become better people as a result of practicing it. - Joe Mullally, computer salesman

Close