Lychrel numbers: Difference between revisions

Content added Content deleted

Inline

Revision as of 11:47, 20 October 2015

Take an integer n, greater than zero.
Form the next n of its series by reversing the digits of the current n and adding the result to the current n.
Stop when n becomes palindromic - i.e. the digits of n in reverse order == n.

The above recurrence relation when applied to most starting numbers n = 1, 2, ... terminates in a palindrome quite quickly, for example if n₀ = 12 we get

12
12 + 21 = 33, a palindrome!

And if n₀ = 55 we get

55
55 + 55 = 110
110 + 011 = 121, a palindrome!

Notice that the check for a palindrome happens after an addition.

Some starting numbers seem to go on forever; the recurrence relation for 196 has been calculated for millions of repetitions forming numbers with millions of digits, without forming a palindrome. These numbers that do not end in a palindrome are called Lychrel numbers.
For the purposes of this task a Lychrel number is any starting number that does not form a palindrome within 500 (or more) iterations.

Seed and related Lychrel numbers

Any integer produced in the sequence of a Lychrel number is also a Lychrel number.
In general, any sequence from one Lychrel number might converge to join the sequence from a prior Lychrel number candidate; for example the sequences for the numbers 196 and then 689 begin:

196
196 + 691 = 887
887 + 788 = 1675
1675 + 5761 = 7436
7436 + 6347 = 13783
13783 + 38731 = 52514
52514 + 41525 = 94039
...


689
689 + 986 = 1675
1675 + 5761 = 7436
...

So we see that the sequence starting with 689 converges to, and continues with the same numbers as that for 196. Because of this we can further split the Lychrel numbers into true Seed Lychrel number candidates, and Related numbers that produce no palindromes but have integers in their sequence seen as part of the sequence generated from a lower Lychrel number.

Task

Find the number of seed Lychrel number candidates and related numbers for n in the range 1..10000 inclusive. (With that iteration limit of 500).
Print the number of seed Lychrels found; the actual seed Lychrels; and just the number of relateds found.
Print any seed Lychrel or related number that is itself a palindrome.

Show all output here.

References

What's special about 196? Numberphile video.
A023108 Positive integers which apparently never result in a palindrome under repeated applications of the function f(x) = x + (x with digits reversed).
Status of the 196 conjecture? Mathoverflow.

Common Lisp

<lang lisp>(defun Lychrel (number &optional (max 500))

"Returns T if number is a candidate Lychrel (up to max iterations), and a second value with the sequence of sums"
 (do* ((n number (+ n (parse-integer rev-str)))
       (n-str (write-to-string n) (write-to-string n))
       (rev-str (reverse n-str) (reverse n-str))
       (i 0 (1+ i))
       (list (list n) (cons n list)) )
   ((or (> i max) (and (string= n-str rev-str) (> i 0))) (values (not (string= n-str rev-str)) (nreverse list)))))

(defun Lychrel-test (n &optional (max 500))

"Tests the first n numbers up to max number of iterations"
 (let ((seeds nil)
       (related 0)
       (palyndromes nil) )
   (dotimes (i (1+ n))
     (multiple-value-bind (Lychrel-p seq) (Lychrel i max)
       (when Lychrel-p
         (if (find seq seeds :test #'intersection :key #'cdr)
           (incf related)
           (push (cons i seq) seeds) )
         (when (= i (parse-integer (reverse (write-to-string i))))
           (push i palyndromes) ))))
   (format T "Testing numbers: 1 to ~D~%Iteration maximum: ~D~%~%Number of Lychrel seeds found: ~d => ~a~%~
   Number of related found: ~D~%Palyndrome Lychrel numbers: ~D => ~a~%"
   n max (length seeds) (nreverse (mapcar #'car seeds)) related (length palyndromes) (nreverse palyndromes)) ))

</lang>

Output:

>(lychrel-test 10000)
Testing numbers: 1 to 10000
Iteration maximum: 500

Number of Lychrel seeds found: 5 => (196 879 1997 7059 9999)
Number of related found: 244
Palyndrome Lychrel numbers: 3 => (4994 8778 9999)
NIL

D

Translation of: Python

<lang d>import std.stdio, std.conv, std.range, std.typecons, std.bigInt;

auto rev(in BigInt n) {

   return n.text.retro.text.to!BigInt;

}

alias Res = Tuple!(bool, BigInt);

Res lychel(BigInt n) {

   static Res[BigInt] cache;
   if (n in cache)
       return cache[n];

   auto r = n.rev;
   auto res = Res(true, n);
   immutable(BigInt)[] seen;
   foreach (immutable i; 0 .. 1_000) {
       n += r;
       r = n.rev;
       if (n == r) {
           res = Res(false, BigInt(0));
           break;
       }
       if (n in cache) {
           res = cache[n];
           break;
       }
       seen ~= n;
   }
   
   foreach (x; seen)
       cache[x] = res;
   return res;

}

void main() {

   BigInt[] seeds, related, palin;

   foreach (immutable i; BigInt(1) .. BigInt(10_000)) { // 1_000_000
       const tf_s = i.lychel;
       if (!tf_s[0])
           continue;
       (i == tf_s[1] ? seeds : related) ~= i;
       if (i == i.rev)
           palin ~= i;
   }
   
   writeln(seeds.length, " Lychel seeds: ", seeds);
   writeln(related.length, " Lychel related");
   writeln(palin.length, " Lychel palindromes: ", palin);

}</lang>

Output:

5 Lychel seeds: [196, 879, 1997, 7059, 9999]
244 Lychel related
3 Lychel palindromes: [4994, 8778, 9999]

Almost two times slower than the Python version with LDC2, probably because of the lower efficiency of the big integers.

Fortran

Fortran lacks built-in support for arbitrary-precision arithmetic, but fortunately, long addition is easily implemented. Digit strings are preferable anyway, as with the numbers in normal variables, there would be a lot of struggle in extracting the base ten digits - unless one was working on a base ten computer such as the IBM1620. A convenient approach is to have an array to hold the digits, with element zero having the count of digits in use. Alas, if one tries to use small digits (such as INTEGER*1) a count cannot exceed +127 and one soon finds that this problem needs longer digit strings. One could convert to using INTEGER*2, but instead the latter-day feature of defining a "type" can be employed to create a compound entity with a large integer for the count and still INTEGER*1 for the digits. An alternative for the digits would be to use a CHARACTER array, and rely on functions CHAR and ICHAR to get at the numerical values.

Arithmetic on BIGINT values is easy when only addition is needed, and there might arise special properties, for instance, imagine equivalencing the digits to a sequence of 64-bit integers and performing the addition 64-bits at a time and thus eight digits in each blow! Alas, alignment will be a problem as a digit string will not often be a multiple of eight in length and the requirement to access the digits from both ends of the string exacerbates the problem. On the other hand, one-byte integers are all very well, but the cpu will have to struggle to isolate each digit when accessing memory, as with 32-bit words or even 64-bit words. But that's a problem for the cpu. Here, the method has two parts: first is to perform the addition of all the digits in one go via a FOR ALL statement, and who knows, perhaps it will all happen in parallel. Second is a fixup pass, to spread the carries appropriately. This will involve multiple passes through the array memory so it might be better to employ a single pass with proper attention to carries: a complex loop (whose code will be in the cpu's on-chip memory) that makes lesser demands on memory transfer via one pass only.

So the plan is to have an array STASH of BIGINT elements, and auxiliary arrays that finger elements in this stash. These arrays are needed to form the various lists of numbers of one sort or another that will be kept, and some searched. Such lists can have their elements juggled easily (being simple integers) as opposed to moving BIGINT elements about. Trial runs showed that a list may have thousands of numbers, and a many linear searches of so many can be expected to be slow - indeed, a pause in the production of results was apparent. So, a binary search. But this requires a sorted list. The Combsort works well, but greatly slowed execution because the complete sorting of a list takes time when it is done often. Fortunately, most additions to the lists are in increasing numerical order, so Insertionsort proved far better - though in the event the speed was about the same as for a linear search with no sorting. Ah well. Otherwise, one would be stuck with having a sorted area and an overflow area (unsorted) for a compound search, with a full sort whenever the overflow area becomes big enough. Or, escalating to a hash-based scheme. All added effort in programming. As distinct from languages already offering associative arrays as built-in facilities.

The growth of the numbers was interesting, so a simple investigation: what of the growth per step for 196? The digit strings lengthened in a linear-looking way, so, what of a plot of step as x, vs Log10(n) as y? The result for 500 numbers went from step 0 and Log10(196) = 2·292256 to step 499 and 215·266386 and the linear correlation coefficient came out as 1·000 with y = 0·43328*x + 2·1616, which is to say that each advance increased the number by a factor of about 2·7. However, the plot (which alas, can't be posted here) does not show a random scatter about the straight line, it instead shows the points wobbling above and below the fitted line. A plot of the residuals shows the deviations coming in waves, but also cannot be posted here...

The results have oddities: when searching a list of numbers that later advance to palindromes, or a list of number that later advanced to the step limit of 500, it turned out that every success in finding a match occurred on the first step from its starting value.

     SUBROUTINE CROAK(GASP)	!A dying message.
      CHARACTER*(*) GASP	!The message.
       WRITE (6,*) "Oh dear! ",GASP	!The gasp.
       STOP "Alas."		!The death.
     END			!Goodbye, cruel world.

     MODULE LYCHREL SEARCH	!Assistants for the pursuit of Lychrel numbers.
      INTEGER LOTSADIGITS,BASE	!Parameters.
      PARAMETER (LOTSADIGITS = 1000, BASE = 10)	!This should do.
      TYPE BIGINT	!Can't use an element zero as the count, as lots of digits are needed.
       INTEGER LDIGIT	!Count in use.
       INTEGER*1 DIGIT(LOTSADIGITS)	!Stored in increasing powers of BASE.
      END TYPE BIGINT		!No fractional parts.
      INTEGER NSTASH,MSTASH	!Now for my stash.
      PARAMETER (MSTASH = 66666)	!This should be enough.
      TYPE(BIGINT) STASH(MSTASH)	!The work area.
      INTEGER PLIST(0:MSTASH)	!These strings of fingers
      INTEGER LLIST(0:MSTASH)	!Each starting with a count
      INTEGER LYCHREL(0:MSTASH)!Finger BIGINTs in the STASH
      INTEGER L0P(0:MSTASH)	!Without the body of the BIGINT being copied.
      INTEGER LONGESTNUMBER	!Keep track out of curiosity.
      DATA LONGESTNUMBER/0/	!No digits so far.
      CONTAINS		!A miscellany.

       SUBROUTINE BIGWRITE(T,N)!Reveal an annotated bignumber.
        CHARACTER*(*) T	!The text of its name.
        TYPE(BIGINT) N		!The value of its name.
         WRITE (6,1) T,N.LDIGIT,N.DIGIT(N.LDIGIT:1:-1)	!Roll!
   1     FORMAT (A,"(1:",I0,") = ",(300I1))	!This should do.
       END SUBROUTINE BIGWRITE	!Perhaps bigger than Integer*8.

       SUBROUTINE SHOWLIST(BLAH,LIST)	!One can become confused.
        INTEGER LIST(0:MSTASH)	!Explicit bounds prevents confusion.
        CHARACTER*(*) BLAH	!An identifying message.
        CHARACTER*4 ZOT	!Scratchpad.
        INTEGER I,IT		!Stepper.

c REAL*8 V,P !For logarithmic output. c INTEGER J !Another stepper needed.

         WRITE (6,1) BLAH,LIST(0)		!A heading.
   1     FORMAT ("The count for ",A," is ",I0)	!Ah, layout.
         DO I = 1,LIST(0)		!Work through the list.
           WRITE(ZOT,"('#',I3)") I	!Prepare an annotation.
           IT = LIST(I)
           CALL BIGWRITE(ZOT,STASH(IT))	!Show.

c V = 0 !Convert the BIGINT to a floating-point number. c P = 1 !Tracking the powers of BASE, presumed ten. c PP:DO J = STASH(IT).LDIGIT,1,-1 !Start with the highest power. c V = V + STASH(IT).DIGIT(J)/P !Deem it a units digit. c P = P*10 !The next digit will have a lesser power. c IF (P.GT.1000000) EXIT PP !This will do. c END DO PP !On to the next digit. c V = STASH(IT).LDIGIT - 1 + LOG10(V) !Convert. LOG10(196) = 2.29225607135648 c WRITE (6,*) I,V !Reveal.

         END DO			!On to the next.
       END SUBROUTINE SHOWLIST	!Adrift in indirection.

       SUBROUTINE BIGLOAD(A,NUM)	!Shatters a proper number into its digits.

Can't overflow, because the biggest normal integer has far fewer than LOTSADIGITS digits.

        TYPE(BIGINT) A		!The bignumber.
        INTEGER NUM		!The normal integer to put in it.
        INTEGER L,N		!Assistants.
         N = NUM		!A copy that I can damage.
         A.DIGIT = 0		!Scrub, against a future carry..
         L = 0			!No digits so far.
         DO WHILE(N .GT. 0)	!Some number remaining?
           L = L + 1			!Yes. Count another digit.
           A.DIGIT(L) = MOD(N,BASE)	!Place it.
           N = N/BASE			!Reduce the number.
         END DO		!And try again.
         A.LDIGIT = MAX(1,L)	!Zero will have one digit, a zero.
       END SUBROUTINE BIGLOAD	!A small service.

       SUBROUTINE ADVANCE(A,B)	!Advance A, giving B.

C Experiment shows that for 196, log10(v) = 0·43328*step + 2·1616, or, each advance increases by a factor of ~2·7.

        TYPE(BIGINT) A,B	!To be twiddled.
        INTEGER D		!An assistant for carrying.
        INTEGER I		!A stepper.
         B.LDIGIT = A.LDIGIT		!Same size, so far.
         FORALL(I = 1:A.LDIGIT)	!Do these in any order, even in parallel!
    1     B.DIGIT(I) = A.DIGIT(I)			!Add each digit
    2                + A.DIGIT(A.LDIGIT - I + 1)	! to its other-end partner.
         B.DIGIT(B.LDIGIT + 1) = 0	!Perhaps another digit will be needed shortly.
         DO I = 1,B.LDIGIT		!Now slow down and taste the carry.
           D = B.DIGIT(I) - BASE	!Allowable digits are 0:BASE - 1.
           IF (D.GE.0) THEN		!So, has this digit overflowed?
             B.DIGIT(I) = D			!Yes. Only addition, so no div and mod stuff.
             B.DIGIT(I + 1) = B.DIGIT(I + 1) + 1	!Carry one up, corresponding to subtracting one BASE down.
           END IF			!So much for that digit.
         END DO		!On to the next digit, of higher power.
         IF (D.GE.0) THEN	!A carry from the highest digit?
           IF (B.LDIGIT .GE. LOTSADIGITS) CALL CROAK("Overflow!")	!Oh dear.
           B.LDIGIT = B.LDIGIT + 1	!NB! Always there is room left for ONE more digit.
           LONGESTNUMBER = MAX(B.LDIGIT,LONGESTNUMBER)	!Perhaps a surprise awaits.
         END IF		!Avoids overflow testing for every carry above.
       END SUBROUTINE ADVANCE	!That was fun!

       LOGICAL FUNCTION PALINDROME(N)	!Perhaps a surprise property?

Calls a one-digit number palindromic through the execution of vacuous logic.

        TYPE(BIGINT) N	!The big number to inspect.
         PALINDROME = ALL(N.DIGIT(1:N.LDIGIT/2)	!Compare each digit in the first half...
    1                 .EQ.N.DIGIT(N.LDIGIT:N.LDIGIT/2 + 1:-1))	!To its opposite digit in the second. Whee!
       END FUNCTION PALINDROME	!If an odd number of digits, ignores the middle digit.

       INTEGER FUNCTION ORDER(A,B)	!Does B follow A?
        TYPE(BIGINT) A,B	!The two numbers.
        INTEGER I		!A stepper.
         IF (A.LDIGIT - B.LDIGIT) 1,10,2	!First, compare the lengths.
   1     ORDER = +1		!B has more digits.
        RETURN			!So, A must be smaller: in order.
   2     ORDER = -1		!A has more digits.
        RETURN			!So B must be smaller: reverse order.

Compare the digits of the two numbers, known to be of equal length.

  10     DO 11 I = A.LDIGIT,1,-1	!The last digit has the highest power.
           IF (A.DIGIT(I) - B.DIGIT(I)) 1,11,2	!Compare the digits.
  11     CONTINUE		!If they match, continue with the next digit.
         ORDER = 0		!If all match, A = B.
       END FUNCTION ORDER	!Ah, three-way tests...

       SUBROUTINE COMBSORT(XNDX)	!Sort according to STASH(XNDX)) by reordering XNDX.

Crank up a Comb sort of array STASH as indexed by XNDX.

        INTEGER XNDX(0:),T	!The index to be rearranged.
        INTEGER I,H		!Tools. H ought not be a small integer.
        LOGICAL CURSE		!Annoyance.
         H = XNDX(0) - 1	!Last - First, and not +1.
         IF (H.LE.0) GO TO 999	!Ha ha.
   1     H = MAX(1,H*10/13)	!The special feature.
         IF (H.EQ.9 .OR. H.EQ.10) H = 11	!A twiddle.
         CURSE = .FALSE.		!So far, so good.
         DO I = XNDX(0) - H,1,-1	!If H = 1, this is a BubbleSort.
           IF (ORDER(STASH(XNDX(I)),STASH(XNDX(I + H))) .LT. 0) THEN	!One compare.
             T=XNDX(I); XNDX(I)=XNDX(I+H); XNDX(I+H)=T		!One swap.
             CURSE = .TRUE.				!One curse.
           END IF				!One test.
         END DO			!One loop.
         IF (CURSE .OR. H.GT.1) GO TO 1!Work remains?
 999    RETURN			!If not, we're done.
       END SUBROUTINE COMBSORT	!Good performance, and simple.

       SUBROUTINE INSERTIONSORT(XNDX)	!Adjust XNDX according to STASH(XNDX)

Crank up an Insertion sort of array STASH as indexed by XNDX.

        INTEGER XNDX(0:),IT	!The index to be prepared, and a safe place.
        INTEGER I,L		!Fingers.
         DO L = 2,XNDX(0)	!Step along the array.
           IF (ORDER(STASH(XNDX(L - 1)),STASH(XNDX(L))) .LT. 0) THEN	!Disorder?
             I = L		!Yes. Element L belongs earlier.
             IT = XNDX(L)	!Save it so that others can be shifted up one.
   1         XNDX(I) = XNDX(I - 1)	!Shift one.
             I = I - 1		!The next candidate back.
             IF (I.GT.1 .AND. ORDER(STASH(XNDX(I - 1)),	!Do I have to go further back?
    1                               STASH(IT)).LT.0) GO TO 1	!Yes.
             XNDX(I) = IT	!Done. Place it in the space created.
           END IF		!So much for that comparison.
         END DO		!On to the next.
       END SUBROUTINE INSERTIONSORT	!Swift only if the array is nearly in order.

       INTEGER FUNCTION FOUNDIN(XNDX,X)	!Search STASH(XNDX) for X.

Crank up a binary serach. This uses EXCLUSIVE bounds.

        INTEGER XNDX(0:)	!The list of elements.
        TYPE(BIGINT) X		!The value to be sought.
        INTEGER L,P,R		!Fingers for the binary search.
         L = 0			!Establish outer bounds.
         R = XNDX(0) + 1	!One before, and one after, the first and last.
   1     P = (R - L)/2		!Probe point offset. Beware integer overflow with (L + R)/2.
         IF (P.LE.0) THEN	!Is the search span exhausted?
           FOUNDIN = -L	!Alas.
          RETURN		!Nothing more to search.
         END IF		!Otherwise, STASH(XNDX(L + 1)) <= X <= STASH(XNDX(R - 1))
         P = L + P		!Convert from offset to probe point.
         IF (ORDER(X,STASH(XNDX(P)))) 2,4,3	!Compare X to the probe point's value.
   2     L = P			!STASH(XNDX(P)) < X: advance L to P.
         GO TO 1		!Try again.
   3     R = P			!X < STASH(XNDX(P)): retract R to P.
         GO TO 1		!Try again.

Caught it! X = STASH(XNDX(P)) - the result indexes XNDX, not STASH.

   4     FOUNDIN = P		!So, X is found, here! *Not* at P, but at XNDX(P).
       END FUNCTION FOUNDIN	!Hopefully, without array copy-in, copy-out.

       SUBROUTINE INSPECT(S1,S2,ENUFF)	!Follow the Lychrel protocol.

Careful! A march is stopped on encountering a palindrome, BUT, the starting value is not itself checked.

        INTEGER S1,S2		!Start and stop values.
        INTEGER ENUFF		!An infinite trail can't be followed.
        INTEGER STEP,SEED	!Counts the advances along the long march.
        INTEGER DEJAVU,IT	!Assistants.
        INTEGER LP,NP,LL,NL	!Counters for various odd outcomes.
         NP = 0		!No palindromic stops.
         LP = 0		!Nor any that head for one.
         NL = 0		!No neverending sequences seen.
         LL = 0		!Nor any that head for one.
         WRITE (6,10) S1,S2,ENUFF	!Announce the plan.
  10     FORMAT ("Starting values ",I0," to ",I0,"; step limit ",I0)

         DO SEED = S1,S2	!Here we go.
           IT = NSTASH + 1		!First unused element.
           IF (IT.GE.MSTASH) CALL CROAK("Stash full!")	!Maybe not!
           CALL BIGLOAD(STASH(IT),SEED)	!The starting value.

c CALL BIGWRITE("N0",STASH(IT)) !Show it.

     CHASE:DO STEP = 1,ENUFF		!How long is a piece of string? Long enough.
             CALL ADVANCE(STASH(IT),STASH(IT + 1))	!Keeping the original, in case of stashing.

c CALL BIGWRITE("N1",STASH(IT + 1)) !Progress may be of interest.

             DEJAVU = FOUNDIN(PLIST,STASH(IT + 1))	!A value known to later become a plaindrome?
             IF (DEJAVU .GT. 0) THEN			!It being amongst those stashed for that cause.

c WRITE (6,*) SEED,STEP,"Deja vu! List#",DEJAVU

               LP = LP + 1				!Count a late starter.
               CALL SLURP(PLIST)			!Save elements NSTASH + 1 to IT.
               EXIT CHASE				!Not IT + 1, as it is already stashed - being found, like.
             END IF					!So much for prospective palindromes.
             IF (PALINDROME(STASH(IT + 1))) THEN	!Attained an actual palindrome?

c WRITE (6,*) SEED,STEP,"Palindrome!" !Yes!

               NP = NP + 1				!Count a proper palendrome.
               CALL SLURP(PLIST)			!And remember all steps up to it.
               EXIT CHASE				!This is a pretext for ending.
             END IF					!Since one could advance past a palindrome, and then find another.
             DEJAVU = FOUNDIN(LYCHREL,STASH(IT + 1))	!A value known to later pass ENUFF?
             IF (DEJAVU .GT. 0) THEN			!If so, there is no need to follow that march again.

c WRITE (6,*) SEED,STEP,"Latecomer! List#",DEJAVU !So this starter has been preempted. c CALL BIGWRITE("Latecomer!",STASH(LYCHREL(DEJAVU))) !Or, just STASH(IT + 1), they being equal.

               LLIST(0) = LLIST(0) + 1			!Count another latecomer.
               LLIST(LLIST(0)) = NSTASH + 1		!This was its starting value.
               IF (PALINDROME(STASH(NSTASH + 1))) THEN	!Perhaps its starting value was a palindrome?
                 L0P(0) = L0P(0) + 1				!Yes! Count another such.
                 L0P(L0P(0)) = NSTASH + 1			!Using a finger, rather than copying a BIGINT.
               END IF					!A Lychrel number whose zeroth step is palindromic.
               LL = LL + 1				!Anyway, this path has joined a known long march.
               CALL SLURP(LYCHREL)			!So, all its steps do so also.
               EXIT CHASE				!Even though its later start might find a palindrome within ENUFF steps.
             END IF					!So much for discoveries at each step.
             IT = IT + 1			!If none of that, accept the value.
             IF (IT.GE.MSTASH) CALL CROAK("Stash filled!")	!Perhaps not.
           END DO CHASE		!And consider what happens after the next advance.

Chase completed. Consider how it ended.

           IF (STEP .GT. ENUFF) THEN	!If we ran out of string, declare a (provisional) Lychrel aspect.
             WRITE (6,*) SEED,"retains Lychrel potential."	!Since a palindrome has not been reached.
             IF (PALINDROME(STASH(NSTASH + 1))) THEN	!Perhaps it started as a palindrome?
               L0P(0) = L0P(0) + 1			!It did!
               L0P(L0P(0)) = NSTASH + 1		!So remember it.
             END IF				!Enough shades of classification.
             NL = NL + 1			!Count another at the end of a long march.
             CALL SLURP(LYCHREL)		!And save the lot, including the final value.
           END IF			!So much for that march.
         END DO		!Start another.

Cast forth a summary.

         WRITE (6,*)
         WRITE (6,11) NL,ENUFF,LL,LYCHREL(0)
  11     FORMAT (I8," starters attained step ",I0," and ",
    1     I0," joined a long march. "
    2     I0," waypoints stashed.")
         CALL SHOWLIST("starters that joined a Long March",LLIST)
         CALL SHOWLIST("Long Marchers starting as plaindromes",L0P)
         WRITE (6,12) NP,LP,PLIST(0)
  12     FORMAT (I8," starters ended as a palindrome, ",
    1     I0," joined a route leading to a palindrome. ",
    2     I0," waypoints stashed.")
        CONTAINS
         SUBROUTINE SLURP(LIST)	!An assistant.
          INTEGER LIST(0:MSTASH)	!Some string of numbers.
          INTEGER J			!A stepper.
           DO J = NSTASH + 1,IT	!Carefully attend to IT.
             LIST(0) = LIST(0) + 1	!Count in another for this list.
             LIST(LIST(0)) = J		!And save a finger to it.
           END DO			!On to the next.
           NSTASH = IT		!The used portion of STASH extends.
           CALL INSERTIONSORT(LIST)	!Speedy, I hope.
         END SUBROUTINE SLURP	!Small, but annoying to enter twice.
       END SUBROUTINE INSPECT	!That was fun.
     END MODULE LYCHREL SEARCH	!Enough of that.

     PROGRAM TEST
     USE LYCHREL SEARCH

Clear my lists.

      LYCHREL(0) = 0	!No Lychrel candidates.
      LLIST(0) = 0	!No latecomers to a Lychrel candidacy sequence.
      PLIST(0) = 0	!No numbers leading to a palindrome.
      L0P(0) = 0	!No Lychrel/latecomers starting as a palindrome.
      NSTASH = 0	!No numbers in my stash.

      CALL INSPECT(1,10000,500)	!Whee!

      WRITE (6,*) "Longest digit string =",LONGESTNUMBER
     END

</lang>

Output: edited to put twenty numbers per line and omit the (1:n) of the output from BIGWRITE...

Starting values 1 to 10000; step limit 500
         196 retains Lychrel potential.
         879 retains Lychrel potential.
        1997 retains Lychrel potential.
        7059 retains Lychrel potential.
        9999 retains Lychrel potential.

       5 starters attained step 500 and 244 joined a long march. 2753 waypoints stashed.
The count for starters that joined a Long March is 244
  295,  394,  493,  592,  689,  691,  788,  790,  887,  978,  986, 1495, 1497, 1585, 1587, 1675, 1677, 1765, 1767, 1855,
 1857, 1945, 1947, 2494, 2496, 2584, 2586, 2674, 2676, 2764, 2766, 2854, 2856, 2944, 2946, 2996, 3493, 3495, 3583, 3585,
 3673, 3675, 3763, 3765, 3853, 3855, 3943, 3945, 3995, 4079, 4169, 4259, 4349, 4439, 4492, 4494, 4529, 4582, 4584, 4619,
 4672, 4674, 4709, 4762, 4764, 4799, 4852, 4854, 4889, 4942, 4944, 4979, 4994, 5078, 5168, 5258, 5348, 5438, 5491, 5493,
 5528, 5581, 5583, 5618, 5671, 5673, 5708, 5761, 5763, 5798, 5851, 5853, 5888, 5941, 5943, 5978, 5993, 6077, 6167, 6257,
 6347, 6437, 6490, 6492, 6527, 6580, 6582, 6617, 6670, 6672, 6707, 6760, 6762, 6797, 6850, 6852, 6887, 6940, 6942, 6977,
 6992, 7076, 7149, 7166, 7239, 7256, 7329, 7346, 7419, 7436, 7491, 7509, 7526, 7581, 7599, 7616, 7671, 7689, 7706, 7761,
 7779, 7796, 7851, 7869, 7886, 7941, 7959, 7976, 7991, 8058, 8075, 8079, 8089, 8148, 8165, 8169, 8179, 8238, 8255, 8259,
 8269, 8328, 8345, 8349, 8359, 8418, 8435, 8439, 8449, 8490, 8508, 8525, 8529, 8539, 8580, 8598, 8615, 8619, 8629, 8670,
 8688, 8705, 8709, 8719, 8760, 8778, 8795, 8799, 8809, 8850, 8868, 8885, 8889, 8899, 8940, 8958, 8975, 8979, 8989, 8990,
 9057, 9074, 9078, 9088, 9147, 9164, 9168, 9178, 9237, 9254, 9258, 9268, 9327, 9344, 9348, 9358, 9417, 9434, 9438, 9448,
 9507, 9524, 9528, 9538, 9597, 9614, 9618, 9628, 9687, 9704, 9708, 9718, 9777, 9794, 9798, 9808, 9867, 9884, 9888, 9898,
 9957, 9974, 9978, 9988
The count for Long Marchers starting as plaindromes is 3
#  1(1:4) = 4994
#  2(1:4) = 8778
#  3(1:4) = 9999
    3044 starters ended as a palindrome, 6707 joined a route leading to a palindrome. 10403 waypoints stashed.
 Longest digit string =         221

FreeBASIC

<lang freebasic>' version 13-09-2015 ' compile with: fbc -s console

' iteration limit

Define max_it 500

' the highest number to be tested

Define max_number_to_test 10000

Dim As String num, rev Dim As String temp(), store()

Dim As Integer x, x1, palindrome Dim As UInteger it, s, carry, sum, match, seed, related Dim As UInteger num2test, p_count, lychrel_palindrome()

For num2test = 1 To max_number_to_test

   num = Str(num2test)
   rev = num : s = Len(num) - 1
   For x = 0 To s
       rev[s - x] = num[x]
   Next
   ' if num = rev then palindrome = -1 else palindrome = 0
   ' palindrome is set to the result of the compare of num and rev
   palindrome = (num = rev)
   it = 0
   ReDim temp(1 To max_it)
   Do
       carry = 0
       For x = s To 0 Step -1 'add the two numbers
           sum = num[x] + rev[x] + carry
           If sum > (9 + 48 + 48) Then
               num[x] = sum - 10 - 48
               carry = 1
           Else
               num[x] = sum - 48
               carry = 0
           End If
       Next
       If carry = 1 Then num = "1" + num
       it = it + 1 : temp(it) = num
       rev = num : s = Len(num) - 1
       For x = 0 To s
           rev[s - x] = num[x]
       Next
   Loop Until num = rev OrElse it = max_it
   If it = max_it Then
       match = 0
       ' if it's palindrome then save the number
       If palindrome <> 0 Then
           p_count = p_count + 1
           ReDim Preserve lychrel_palindrome(1 To p_count)
           lychrel_palindrome(p_count) = num2test
       End If
       For x = 1 To seed ' check against previous found seed(s)
           For x1 = max_it To 1 Step -1
               If store(x, 1) = temp(x1) Then
                   match = 1
                   related = related + 1
                   Exit For, For
               Else
                   If Len(store(x,1)) > Len(temp(x1)) Then
                       Exit For
                   End If
               End If
           Next
       Next
       ' no match found then it's a new seed, store it
       If match = 0 Then
           seed = seed + 1
           ReDim Preserve store(seed, 1)
           store(seed, 0) = Str(num2test)
           store(seed, 1) = temp(max_it)
       End If
   End If

Print Print " Testing numbers: 1 to "; Str(max_number_to_test) Print " Iteration maximum: ";Str(max_it) Print Print " Number of Lychrel seeds: "; seed Print " Lychrel number: "; For x = 1 To seed : Print store(x,0); " "; : Next : Print Print " Number of relateds found: "; related Print " Lychrel numbers that are palindromes: "; p_count Print " Lychrel palindromes: "; For x = 1 To p_count : Print lychrel_palindrome(x); " "; : Next : Print Print

' empty keyboard buffer While Inkey <> "" : Var _key_ = Inkey : Wend Print : Print "hit any key to end program" Sleep End</lang>

Output:

                      Testing numbers: 1 to 10000
                    Iteration maximum: 500

              Number of Lychrel seeds: 5
                       Lychrel number: 196 879 1997 7059 9999 
             Number of relateds found: 244
 Lychrel numbers that are palindromes: 3
                  Lychrel palindromes: 4994 8778 9999

Go

<lang go>package main

import ( "flag" "fmt" "math" "math/big" "os" )

var maxRev = big.NewInt(math.MaxUint64 / 10) // approximate var ten = big.NewInt(10)

// Reverse sets `result` to the value of the base ten digits of `v` in // reverse order and returns `result`. // Only handles positive integers. func reverseInt(v *big.Int, result *big.Int) *big.Int { if v.Cmp(maxRev) <= 0 { // optimize small values that fit within uint64 result.SetUint64(reverseUint64(v.Uint64())) } else { if true { // Reverse the string representation s := reverseString(v.String()) result.SetString(s, 10) } else { // This has fewer allocations but is slower: // Use a copy of `v` since we mutate it. v := new(big.Int).Set(v) digit := new(big.Int) result.SetUint64(0) for v.BitLen() > 0 { v.QuoRem(v, ten, digit) result.Mul(result, ten) result.Add(result, digit) } } } return result }

func reverseUint64(v uint64) uint64 { var r uint64 for v > 0 { r *= 10 r += v % 10 v /= 10 } return r }

func reverseString(s string) string { b := make([]byte, len(s)) for i, j := 0, len(s)-1; j >= 0; i, j = i+1, j-1 { b[i] = s[j] } return string(b) }

var known = make(map[string]bool)

func Lychrel(n uint64, iter uint) (isLychrel, isSeed bool) { v, r := new(big.Int).SetUint64(n), new(big.Int) reverseInt(v, r) seen := make(map[string]bool) isLychrel = true isSeed = true for i := iter; i > 0; i-- { str := v.String() if seen[str] { //log.Println("found a loop with", n, "at", str) isLychrel = true break } if ans, ok := known[str]; ok { //log.Println("already know:", str, ans) isLychrel = ans isSeed = false break } seen[str] = true

v = v.Add(v, r) //log.Printf("%v + %v = %v\n", str, r, v) reverseInt(v, r) if v.Cmp(r) == 0 { //log.Println(v, "is a palindrome,", n, "is not a Lychrel number") isLychrel = false isSeed = false break } } for k := range seen { known[k] = isLychrel } //if isLychrel { log.Printf("%v may be a Lychrel number\n", n) } return isLychrel, isSeed }

func main() { max := flag.Uint64("max", 10000, "search in the range 1..`N` inclusive") iter := flag.Uint("iter", 500, "limit palindrome search to `N` iterations") flag.Parse() if flag.NArg() != 0 { flag.Usage() os.Exit(2) }

fmt.Printf("Calculating using n = 1..%v and %v iterations:\n", *max, *iter) var seeds []uint64 var related int var pals []uint64 for i := uint64(1); i <= *max; i++ { if l, s := Lychrel(i, *iter); l { if s { seeds = append(seeds, i) } else { related++ } if i == reverseUint64(i) { pals = append(pals, i) } } }

fmt.Println(" Number of Lychrel seeds:", len(seeds)) fmt.Println(" Lychrel seeds:", seeds) fmt.Println(" Number of related:", related) fmt.Println("Number of Lychrel palindromes:", len(pals)) fmt.Println(" Lychrel palindromes:", pals) }</lang>

Output:

Calculating using n = 1..10000 and 500 iterations:
      Number of Lychrel seeds: 5
                Lychrel seeds: [196 879 1997 7059 9999]
            Number of related: 244
Number of Lychrel palindromes: 3
          Lychrel palindromes: [4994 8778 9999]

J

Reverse digits:

<lang J>revdig=:('x',~|.)&.":"0</lang>

Note that we need extended precision numbers because 500 iterations gets us into very large numbers even when we start small. For example, starting from 12:

<lang J> (+revdig)^:500(12) 989330226271793404132120335101444022368928728236373385750622261099268167362912850818170039990942038798808908830140199820181718948328173760873880172226156484473632718819962221534191534021132404387162721132989</lang>

Test whether a number is a lychrel (true or related) number within that 500 iteration limit:

<lang J>lychrel500=: (~: revdig)@((+^:~: revdig)^:500)@(+revdig)"0</lang>

Number of these lychrel numbers not exceeding 10000 (we start from 0 here, because that's natural for J's primitives, so we need 10001 integers if we are to reach 10000):

<lang J> #L=:I.lychrel500 i.10001 249</lang>

(What are they? Note that this isn't a task requirement - just curiosity.)

<lang J> 3 83$L

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 3493 3495 3583 3585 3673 3675 3763 3765 3853 3855 3943 3945 3995 4079 4169 4259 4349 4439 4492 4494 4529 4582 4584 4619 4672 4674 4709 4762 4764 4799 4852 4854 4889 4942 4944 4979 4994 5078 5168 5258 5348 5438 5491 5493

5528 5581 5583 5618 5671 5673 5708 5761 5763 5798 5851 5853 5888 5941 5943 5978 5993 6077 6167 6257 6347 6437 6490 6492 6527 6580 6582 6617 6670 6672 6707 6760 6762 6797 6850 6852 6887 6940 6942 6977 6992 7059 7076 7149 7166 7239 7256 7329 7346 7419 7436 7491 7509 7526 7581 7599 7616 7671 7689 7706 7761 7779 7796 7851 7869 7886 7941 7959 7976 7991 8058 8075 8079 8089 8148 8165 8169 8179 8238 8255 8259 8269 8328 8345 8349 8359 8418 8435 8439 8449 8490 8508 8525 8529 8539 8580 8598 8615 8619 8629 8670 8688 8705 8709 8719 8760 8778 8795 8799 8809 8850 8868 8885 8889 8899 8940 8958 8975 8979 8989 8990 9057 9074 9078 9088 9147 9164 9168 9178 9237 9254 9258 9268 9327 9344 9348 9358 9417 9434 9438 9448 9507 9524 9528 9538 9597 9614 9618 9628 9687 9704 9708 9718 9777 9794 9798 9808 9867 9884 9888 9898 9957 9974 9978 9988 9999</lang>

To figure out which of these lychrel numbers were "true" lychrel numbers, we will need to work with sequences of sums seeded from these numbers. So let's just find those sequences:

<lang J> S=:(+revdig)^:(i.501)"0 L</lang>

And, let's take a peek at some of the numbers in these sequences (the first 10 values in each lychrel sequence, starting from the first lychrel candidate seeds):

So most of these are related... which ones are not? (An integer is owned if it is in the sequence for this lychrel candidate or for any previous candidates. A lychrel candidate is a true lychrel number if none of its sequence is owned by any previous candidate.)

<lang J> owned=: <@~.@,\S

  #T=: (-. (<"1 S) +./@e.&> a:,}:owned)#L

5

196 879 1997 7059 9999</lang>

And, with that, we can find the count of "just related" lychrel numbers:

And, finally, which of the (true or related) lychrel numbers were themselves palindromes?

<lang J> (#~(=revdig))L 4994 8778 9999</lang>

To reiterate, here's the collected definitions with the task required results (everything above this point was basically just documentation - J tends to need that kind of documentation, because of the nature of the language):

<lang J> revdig=:('x',~|.)&.":"0

  lychrel500=: (~: revdig)@((+^:~: revdig)^:500)@(+revdig)"0
  L=:I.lychrel500 i.10001
  S=:(+revdig)^:(i.501)"0 L
  owned=: <@~.@,\S
  #T=: (-. (<"1 S) +./@e.&> a:,}:owned)#L

5

196 879 1997 7059 9999

  L -&# T

244

  (#~(=revdig))L

4994 8778 9999</lang>

T is the "seed" or "true" lychrel numbers, and #T is how many of them we found. L is all of the candidates (both seeds and relateds), so the difference in the lengths of L and T is the number of relateds.

Perl 6

Works with: Rakudo version 2015-10-10

<lang perl6>my @lychrels; my @palindromes; my @seeds; my $max = 500;

for 1 .. 10000 -> $int {

   my @test;
   my $count = 0;
   @lychrels.push( $int => [@test] ) if lychrel($int);

   sub lychrel (Int $l) {
       return True if $count++ > $max;
       @test.push: my $m = $l + $l.flip;
       return False if $m == $m.flip;
       lychrel($m);
   }

}

@seeds = @lychrels[0]; for @lychrels -> $l {

   @palindromes.push: $l.key if $l.key == $l.key.flip;
   my $trial = 0;
   for @seeds -> $s {
       last if any($s.value) ~~ any($l.value);
       $trial++;
   }
   @seeds.push: $l if $trial == +@seeds;

}

say " Number of Lychrel seed numbers < 10_000: ", +@seeds; say " Lychrel seed numbers < 10_000: ", join ", ", @seeds>>.keys; say "Number of Lychrel related numbers < 10_000: ", +@lychrels -@seeds; say " Number of Lychrel palindromes < 10_000: ", +@palindromes; say " Lychrel palindromes < 10_000: ", join ", ", @palindromes;</lang>

Output:

   Number of Lychrel seed numbers < 10_000: 5
             Lychrel seed numbers < 10_000: 196, 879, 1997, 7059, 9999
Number of Lychrel related numbers < 10_000: 244
    Number of Lychrel palindromes < 10_000: 3
              Lychrel palindromes < 10_000: 4994, 8778, 9999

PicoLisp

<lang PicoLisp>(de pali? (N)

  (let N (chop N)
     (= N (reverse N)) ) )

(de lychrel (A)

  (let 
     (R NIL
        Lst
        (make
           (for X A
              (let (N X  C 500)
                 (while
                    (and
                       (inc 'N (format (flip (chop N))))
                       (gt0 (dec 'C))
                       (not (pali? N)) ) )
                 (and (=0 C) (link X) ) ) ) )
        Lst22
        (by
           '((N)
              (let (X N  C 3)
                 (prog1
                    (bool
                       (or
                          (member (+ N (format (flip (chop N)))) R)
                          (find
                             '((N) (member N R))
                             (make
                                (do C
                                   (link (inc 'X (format (flip (chop X))))) ) ) ) ) )
                 (do C
                    (push1
                       'R
                       (inc 'N (format (flip (chop N)))) ) ) ) ) )
           group
           Lst )
        P (filter pali? Lst) )
     (prinl
        "Using n = 1..10000 and limiting each search to 500 reverse-digits-and-adds" )
     (prinl
        "  Number of Lychrel numbers: "
        (length (car Lst22)) )
     (prin "    Lychrel numbers: ")
     (println (car Lst22))
     (prinl
        "  Number of Lychrel related: "
        (length (cadr Lst22)) )
     (prinl
        "  Number of Lychrel palindroms: "
        (length P) )
     (prin "    Lychrel palindromes: ")
     (println P) ) )

(lychrel 10000)

(bye)</lang>

Output:

Using n = 1..10000 and limiting each search to 500 reverse-digits-and-adds
  Number of Lychrel numbers: 5
    Lychrel numbers: (196 879 1997 7059 9999)
  Number of Lychrel related: 244
  Number of Lychrel palindroms: 3
    Lychrel palindromes: (4994 8778 9999)

Python

<lang python>from __future__ import print_function

def add_reverse(num, max_iter=1000):

   i, nums = 0, {num}
   while True:
       i, num = i+1, num + reverse_int(num)
       nums.add(num)
       if reverse_int(num) == num or i >= max_iter:
           break
   return nums

@functools.lru_cache(maxsize=2**20)

def reverse_int(num):

   return int(str(num)[::-1])

def split_roots_from_relateds(roots_and_relateds):

   roots = roots_and_relateds[::]
   i = 1
   while i < len(roots):
       this = roots[i]
       if any(this.intersection(prev) for prev in roots[:i]):
           del roots[i]
       else:
           i += 1
   root = [min(each_set) for each_set in roots]
   related = [min(each_set) for each_set in roots_and_relateds]
   related = [n for n in related if n not in root]
   return root, related

def find_lychrel(maxn, max_reversions):

   'Lychrel number generator'
   series = [add_reverse(n, max_reversions*2) for n in range(1, maxn + 1)]
   roots_and_relateds = [s for s in series if len(s) > max_reversions]
   return split_roots_from_relateds(roots_and_relateds)

if __name__ == '__main__':

   maxn, reversion_limit = 10000, 500
   print("Calculations using n = 1..%i and limiting each search to 2*%i reverse-digits-and-adds"
         % (maxn, reversion_limit))
   lychrel, l_related = find_lychrel(maxn, reversion_limit)
   print('  Number of Lychrel numbers:', len(lychrel))
   print('    Lychrel numbers:', ', '.join(str(n) for n in lychrel))
   print('  Number of Lychrel related:', len(l_related))
   #print('    Lychrel related:', ', '.join(str(n) for n in l_related))
   pals = [x for x in lychrel + l_related  if x == reverse_int(x)]
   print('  Number of Lychrel palindromes:', len(pals))
   print('    Lychrel palindromes:', ', '.join(str(n) for n in pals))</lang>

Output:

Calculations using n = 1..10000 and limiting each search to 2*500 reverse-digits-and-adds
  Number of Lychrel numbers: 5
    Lychrel numbers: 196, 879, 1997, 7059, 9999
  Number of Lychrel related: 244
  Number of Lychrel palindromes: 3
    Lychrel palindromes: 9999, 4994, 8778

If we test the numbers in ascending order, many of them would have been encountered when checking smaller numbers (i.e. 10 is seen when testing 5), caching them causes a large performance boost, more so with larger ranges. <lang python>from __future__ import print_function

def rev(n): return int(str(n)[::-1])

def lychel(n, cache = {}):

   if n in cache: return cache[n]

   n0, r = n, rev(n)
   res, seen = (True, n), []
   for i in range(1000):
       n += r
       r = rev(n)
       if n == r:
           res = (False, 0)
           break
       if n in cache:
           res = cache[n]
           break
       seen.append(n)

   for x in seen: cache[x] = res
   return res

seeds, related, palin = [], [], []

for i in range(1, 1000000):

   tf, s = lychel(i)
   if not tf: continue
   (seeds if i == s else related).append(i)
   if i == rev(i): palin.append(i)

print("%d Lychel seeds:"%len(seeds), seeds) print("%d Lychel related" % len(related)) print("%d Lychel palindromes:" % len(palin), palin)</lang>

Racket

<lang racket>#lang racket (require racket/splicing)

(define (reverse-digits_10 N)

 (let inr ((n N) (m 0))
   (match n
     [0 m]
     [(app (curryr quotient/remainder 10) q r)
      (inr q (+ r (* 10 m)))])))

(define (palindrome?_10 n)

 (= n (reverse-digits_10 n)))

hash of integer? -> one of 'seed 'related #f

(splicing-let ((memo# (make-hash)))

 (define (generate-lychrel?-chain i i-rev n acc)
   (cond
     [(zero? n) ; out of steam
      (cons 'seed acc)]
     [else
      (let* ((i+ (+ i i-rev)) (i+-rev (reverse-digits_10 i+)))
        (cond
          [(= i+ i+-rev) ; palindrome breaks the chain
           (cons #f acc)]
          [(eq? 'related (hash-ref memo# i+ #f)) ; deja vu
           (cons 'related acc)]
          [else ; search some more
           (generate-lychrel?-chain i+ i+-rev (sub1 n) (cons i+ acc))]))]))
 
 ;; returns 'seed, 'related or #f depending of the Lychrel-ness of a number
 (define (lychrel-number? i #:n (n 500))
   (match (hash-ref memo# i 'unfound)
     ['unfound
      (match (generate-lychrel?-chain i (reverse-digits_10 i) n null)
        [(cons 'related chain) 'related]
        [(cons (and seed (or (and 'seed (app (λ (_) 'related) related?))
                             (and #f (app (λ (_) #f) related?))))
               chain)
         (for ((c (in-list chain))) (hash-set! memo# c related?))
         (hash-set! memo# i seed)
         seed])]
     [seed/related/false seed/related/false])))

(module+ main

 (define-values (seeds/r n-relateds palindromes/r)
   (for/fold ((s/r null) (r 0) (p/r null))
             ((i (in-range 1 (add1 10000))))
     (define lych? (lychrel-number? i))
     (define p/r+ (if (and lych? (palindrome?_10 i)) (cons (list i (list lych?)) p/r) p/r))
     (match lych?
       ['seed (values (cons i s/r) r p/r+)]
       ['related (values s/r (add1 r) p/r+)]
       [#f (values s/r r p/r+)])))
 
 (printf #<<EOS

Seed Lychrel numbers: ~a count:~a Related Lychrel numbers: count:~a Palindromic Lychrel numbers: ~a~% EOS

         (reverse seeds/r) (length seeds/r) n-relateds (reverse palindromes/r)))</lang>

Output:

Seed Lychrel numbers:        (196 879 1997 7059 9999) count:5
Related Lychrel numbers:     count:244
Palindromic Lychrel numbers: ((4994 (related)) (8778 (related)) (9999 (seed)))

REXX

<lang rexx>/*REXX program finds and displays Lychrel numbers, related #s, and palindromes*/ numeric digits 5000 /*ensure enough decimal digits for adds*/ limit=1000 /*limit: number of Lychrel iterations.*/ parse arg high . /*obtain optional argument from the CL.*/ if high= | high==',' then high=10000 /*Not specified? Then use the default.*/ T.=0; @.=0; #.=0; R=; w=length(high) /*W: is used for formatting numbers. */ $= /*list of Lychrel numbers*/

   do j=1  for high;  call Lychrel j;  end  /*j*/   /*find    Lychrel numbers*/

p= /*the list of palindromes*/

   do k=1  for high
   if #.k                  then $=$ k /*build a list of Lychrel numbers.     */
   if T.k                  then R=R k /*  "   "   "   "    "    related nums.*/
   if T.k & k==reverse(k)  then p=p k /*  "   "   "   "    "    palindromes. */
   end /*j*/

say 'Found in the range 1 to' high " (limiting searches to " limit ' steps):' say say right(words($) , w) 'Lychrel numbers:' $ say right(words(R)-words($), w) 'Lychrel related numbers.' say right(words(p) , w) 'Lychrel palindromes:' p exit /*stick a fork in it, we're all done. */ /*────────────────────────────────────────────────────────────────────────────*/ Lychrel: procedure expose limit @. #. T.; parse arg x 1 z /*set X&Z to arg 1*/

        rels=0                                   /*# related nums (so far). */
                  do  limit;     z=z+reverse(z)  /*add the reverse of Z ···  */
                  if z==reverse(z)  then return  /*Is palindromic?   Skip.   */
                  rels=rels+1;  !.rels=z         /*add to the related numbers*/
                  end   /*k*/                    /* [↑]  only DO limit times.*/
        #.x=1                                    /*mark number as a Lychrel. */
        T.x=1;    do a=1  for rels;  _=!.a       /*process "related" numbers.*/
                  if @._  then #.x=0             /*unmark number as Lychrel. */
                          else @._=1             /*  mark    "    "    "     */
                  T._=1                          /*mark number as "related". */
                  end   /*a*/
        return</lang>

output when using the default inputs:

Found in the range  1  to 10000  (limiting searches to  1000  steps):

    5 Lychrel numbers:  196 879 1997 7059 9999
  244 Lychrel related numbers.
    3 Lychrel palindromes:  4994 8778 9999

Rust

This uses the num library for arbitrary-sized integer support as normal integers will overflow.

Cargo.toml

[package]
name = "lychrel"
version = "0.1.0"
authors = ["monsieursquirrel"]

[dependencies]
num = "0.1.27"

src/main.rs <lang rust>extern crate num; use num::FromPrimitive; use num::bigint::BigInt;

use std::collections::HashSet;

/// Reverse a number then add it to the original. fn rev_add(num: &BigInt) -> BigInt {

   let rev_string: String = num.to_string().chars().rev().collect();
   // should be safe, our string is guaranteed to be a number
   let rev_val: BigInt = rev_string.parse().unwrap();
   num + rev_val

}

/// Check if a number is a palindrome when written in base 10. fn is_palindrome(num: &BigInt) -> bool {

   let num_string = num.to_string();
   let rev_string: String = num_string.chars().rev().collect();
   let comp_len = num_string.len() / 2;
   num_string[0..comp_len] == rev_string[0..comp_len]

}

/// Perform a lychrel test on a number, stopping after max_tests /// Returns the sequence of numbers if this number is a lychrel, None otherwise. fn test_lychrel(num: &BigInt, max_tests: usize) -> Option<Vec<BigInt>> {

   let mut sequence = Vec::<BigInt>::new();

   let is_lychrel = (0..max_tests)
       .scan(num.clone(), |current, _| {
           *current = rev_add(current);
           Some(current.clone())
       })
       .inspect(|current| sequence.push(current.clone()))
       .filter(|curent| is_palindrome(curent))
       .next()
       .is_none();

   if is_lychrel {
       Some(sequence)
   }
   else {
       None
   }

}

/// Determine if the sequence for a lychrel number is related to a previously seen sequence fn is_related(seq: &Vec<BigInt>, lychrel_seq_numbers: &HashSet<BigInt>) -> bool {

   seq.iter().filter(|num| lychrel_seq_numbers.contains(num)).next().is_some()

}

/// Find the lychrel numbers up to max_num (inclusive). /// Returns a tuple (lychrel numbers, related numbers, palindrome lychrel/related numbers) fn find_lychrels(max_num: u64, max_tests: usize) -> (Vec<BigInt>, Vec<BigInt>, Vec<BigInt>) {

   // storage for various outputs
   let mut lychrels = Vec::<BigInt>::new();
   let mut relateds = Vec::<BigInt>::new();
   let mut palindrome_lychrels = Vec::<BigInt>::new();

   let mut lychrel_seq_numbers: HashSet<BigInt> = HashSet::new();

   for i in (1..(max_num + 1)) {
       let num = FromPrimitive::from_u64(i).unwrap();
       let maybe_lychrel = test_lychrel(&num, max_tests);

       if let Some(lychrel_seq) = maybe_lychrel {
           // it's a lychrel - check if it's a related number
           let related = is_related(&lychrel_seq, &lychrel_seq_numbers);

           // update our sequences
           for seq_num in lychrel_seq.into_iter() {
               lychrel_seq_numbers.insert(seq_num);
           }

           if !related {
               // the number has a new lychrel sequence, store it
               lychrels.push(num.clone());
           }
           else {
               // just count it as a related number
               relateds.push(num.clone());
           }

           if is_palindrome(&num) {
               // doesn't matter if palindromes are related or not
               palindrome_lychrels.push(num.clone());
           }
       }
   }

   (lychrels, relateds, palindrome_lychrels)

}

fn print_nums(before: &str, numbers: &Vec<BigInt>) {

   print!("{}", before);
   for (i, current) in numbers.iter().enumerate() {
       print!("{}", current);
       if i + 1 < numbers.len() {
           print!(", ");
       }
   }
   println!("");

}

fn main() {

   let max_num: u64 = 10_000;
   let max_tests: usize = 500;

   println!("Calculations using n = 1..{} and limiting each search to {} reverse-digits-and-adds",
       max_num, max_tests);

   let (lychrels, relateds, palindrome_lychrels) = find_lychrels(max_num, max_tests);

   println!("Number of Lychrel numbers: {}", lychrels.len());
   print_nums("Lychrel numbers: ", &lychrels);
   println!("Number of Lychrel related: {}", relateds.len());
   println!("Number of Lychrel palindromes: {}", palindrome_lychrels.len());
   print_nums("Lychrel palindromes: ", &palindrome_lychrels);

}</lang>

Output:

Calculations using n = 1..10000 and limiting each search to 500 reverse-digits-and-adds
Number of Lychrel numbers: 5
Lychrel numbers: 196, 879, 1997, 7059, 9999
Number of Lychrel related: 244
Number of Lychrel palindromes: 3
Lychrel palindromes: 4994, 8778, 9999

Tcl

Works with: Tcl version 8.5

As we collect Lychrel numbers, we can save some time by storing all the members of their orbits in a hash table so that related numbers can be quickly identified. This is what the $visited variable is for: using the keys of a dictionary (or on earlier Tcl versions, an array) for a hash table is a common trick in Tcl. Native bignums mean we don't have to worry about overflow

<lang Tcl>proc pal? {n} {

   expr {$n eq [string reverse $n]}

}

proc step {n} {

   set n_ [string reverse $n]
   set n_ [string trimleft $n_ 0]
   expr {$n + $n_}

}

proc lychrels {{max 10000} {iters 500}} {

   set lychrels {}     ;# true Lychrels
   set visited {}      ;# visited numbers for Related test
   set nRelated 0      ;# count of related numbers seen
   set pals {}         ;# palindromic Lychrels and related

   puts "Searching for Lychrel numbers in \[1,$max\]"
   puts "With a maximum of $iters iterations"

   for {set i 1} {$i <= $max} {incr i} {
       set n $i        ;# seed the sequence
       set seq {}      ;# but don't check the seed, nor remember it for the Related test
       for {set j 0} {$j < $iters} {incr j} {
           set n [step $n]
           dict set seq $n {}
           if {[dict exists $visited $n]} {
               incr nRelated
               if {[pal? $i]} {
                   lappend pals $i
               }
               break   ;# bail out if it's Related
           }
           if {[pal? $n]} {
               break   ;# bail out if it's a palindrome
           }
       }
       if {$j >= $iters} {    ;# the loop was exhausted: must be a Lychrel!
           if {[pal? $i]} {
               lappend pals $i
           }
           lappend lychrels $i
           set visited [dict merge $visited $seq]
       }
   }

   puts "[llength $lychrels] Lychrel numbers found:"
   puts $lychrels
   puts "Count of related numbers: $nRelated"
   puts "Palindromic Lychrel and related numbers: $pals"

}

lychrels</lang>

Output:

Searching for Lychrel numbers in [1,10000]
With a maximum of 500 iterations
5 Lychrel numbers found:
196 879 1997 7059 9999
Count of related numbers: 244
Palindromic Lychrel and related numbers: 4994 8778 9999

zkl

Uses the GNU GMP big int library.

The Lychrel number chain is stored as a long string with '\0' separating each number, which we can then search to find relateds. <lang zkl>var BN=Import("zklBigNum");

  // 192-->"887\01675\07436\013783\0..." ~60k bytes

fcn lychrel(n,returnListof=False){ n=BN(n); //-->Bool|Data(==StringBuf)

  sink:=(if(returnListof) Data(0,String) else Void);
  nls:=(500).pump(sink,'wrap(){
     ns:=n.add(BN(n.toString().reverse())).toString();
     if(ns==ns.reverse()) return(Void.Stop,False);  // not a Lychrel number
     ns
  });
  if(nls) if(returnListof) return(sink.mode(Int).howza(2)) else return(True);
  False;

} fcn isPalindrome(n){ n==n.toString().reverse().toInt() } fcn findSeeds(lychrels){

  seeds:=List(lychrels[0]);
  foreach n,lnns in ([1..].zip(lychrels[1,*])){ ln,seq:=lnns;
     foreach _,s2 in (seeds){

foreach s3 in (seq){ if(Void!=(z:=s2.findString(s3)) and 0==s2[z-1]) break(2); }

     }
     fallthrough{ seeds.append(lnns) }
  }
  seeds.apply("get",0)

}</lang> <lang zkl>lychrels:=[1..0d10_000].filter(lychrel).apply(fcn(n){ T(n,lychrel(n,True)) }); println("[1..10,000] contains ",lychrels.len()," Lychrel numbers.");

lychrels.pump(List,fcn([(n,_)]){ isPalindrome(n) and n or Void.Skip })

  .println("<-- Palindromic Lychrel numbers");

(n:=findSeeds(lychrels)) .println("<-- Lychrel seeds (%d) ==> %d related" .fmt(n.len(),lychrels.len() - n.len()));</lang>

Output:

[1..10,000] contains 249 Lychrel numbers.
L(4994,8778,9999)<-- Palindromic Lychrel numbers
L(196,879,1997,7059,9999)<-- Lychrel seeds (5) ==> 244 related