Lychrel numbers: Difference between revisions

*   [http://mathoverflow.net/questions/117104/status-of-the-196-conjecture/117277#117277 Status of the 196 conjecture?] Mathoverflow.

<br><br>

 

=={{header|ALGOL 68}}==

<br>

Uses the associative array from the Associative array iteration task.

 

# number of additions to attempt before deciding the number is Lychrel #

OD;

print( ( newline ) )

{{out}}

<pre>

There are 3 palindromic Lychrel numbers up to 10000: 4994 8778 9999

</pre>

 

=={{header|BASIC}}==

 

I highly recommend to run this code in QB64. If this code is run in the other related versions, it can take about 20 minutes to run. In QB64 it only takes just seconds (11 seconds in my computer). This code has been tested to calculate up to 15000 numbers. BASIC doesn't have a way to manage such large numbers, but I implemented a way to do the sum through strings (an easy way to create a kind of array).

' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' '

' Lychrel Numbers V1.0 '

 

END FUNCTION

 

Output while running:

=={{header|C++}}==

{{trans|D}}

#include <map>

#include <vector>

 

 

integer rev = 0;

rev = rev * 10 + (n % 10);

n /= 10;

}

 

if (vec.empty())

return;

}

 

std::map<integer, std::pair<bool, integer>> cache;

std::vector<integer> seeds, related, palindromes;

std::pair<bool, integer> p(true, n);

std::vector<integer> seen;

integer rev = reverse(n);

integer sum = n;

sum += rev;

rev = reverse(sum);

p.first = false;

p.second = 0;

}

auto iter = cache.find(sum);

p = iter->second;

break;

print_vector(palindromes);

return 0;

 

{{out}}

 

=={{header|Clojure}}==

(require [clojure.string :as s])

(require [clojure.set :as set-op])

(println count-palindromes "Lychrel palindromes found:" palindrom-n))

)

 

{{out}}

 

=={{header|Common Lisp}}==

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

Number of related found: ~D~%Palyndrome Lychrel numbers: ~D => ~a~%"

n max (length seeds) (nreverse (mapcar #'car seeds)) related (length palyndromes) (nreverse palyndromes)) ))

 

{{out}}

Palyndrome Lychrel numbers: 3 => (4994 8778 9999)

NIL

</pre>

 

=={{header|D}}==

{{trans|Python}}

 

auto rev(in BigInt n) {

writeln(related.length, " Lychrel related");

writeln(palin.length, " Lychrel palindromes: ", palin);

{{out}}

<pre>5 Lychrel seeds: [196, 879, 1997, 7059, 9999]

The growth of the numbers was impressive, 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...

 

SUBROUTINE CROAK(GASP) !A dying message.

CHARACTER*(*) GASP !The message.

WRITE (6,*) "Unused STASH entries =",AVAILS(0)

END

 

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

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre> Testing numbers: 1 to 10000

 

=={{header|Go}}==

 

import (

fmt.Println("Number of Lychrel palindromes:", len(pals))

fmt.Println(" Lychrel palindromes:", pals)

{{out}}

<pre>

 

=={{header|Haskell}}==

 

import Data.List

putStrLn $ show palindromicLychrel ++ " are palindromic Lychrel numbers."

putStrLn $ show lychrelSeeds ++ " are Lychrel seeds."

{{Out}}

<pre>

Reverse digits:

 

 

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:

 

 

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

 

 

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

 

 

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

 

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

 

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:

 

 

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

 

196 887 1675 7436 13783 52514 94039 187088 1067869 10755470

295 887 1675 7436 13783 52514 94039 187088 1067869 10755470

788 1675 7436 13783 52514 94039 187088 1067869 10755470 18211171

790 887 1675 7436 13783 52514 94039 187088 1067869 10755470

 

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

 

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

5

T

 

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?

 

 

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

 

lychrel500=: (~: revdig)@((+^:~: revdig)^:500)@(+revdig)"0

L=:I.lychrel500 i.10001

244

(#~(=revdig))L

 

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

Translation of [[Lychrel_numbers#Python|Python]] via [[Lychrel_numbers#D|D]]

{{works with|Java|8}}

import java.util.*;

 

System.out.printf("%d Lychrel palindromes: %s%n", palin.size(), palin);

}

 

<pre>5 Lychrel seeds: [196, 879, 1997, 7059, 9999]

 

=={{header|jq}}==

# non-negative integers represented as decimal strings:

def add(num1;num2):

end

end ) ;

'''The task'''

 

'''Output'''

{{works with|Julia|1.3}}

 

 

Base.reverse(n::Integer) = parse(BigInt, string(n) |> reverse)

println(length(seeds), " lychrel seeds: ", join(seeds, ", "))

println(length(related), " lychrel related")

 

{{out}}

 

=={{header|Kotlin}}==

 

import java.math.BigInteger

println("\nThere are ${palindromes.size} palindromic Lychrel numbers, namely")

println(palindromes)

 

{{out}}

</pre>

 

A few convenient functions:

Block[{digits = IntegerDigits[n]}, digits == Reverse@digits]

 

palindromeQ@

Catch[Nest[If[palindromeQ[#], Throw[#], nextNumber[#]] &,

 

A list of all integers less 10,000 that do not evolve to a palindrome in 500 iterations

The Lychrel seeds can be obtained from the list of candidates as follows:

NestWhile[(seeds = {seeds, First@#};

test = NestList[nextNumber, First@#, 10];

Rest[#], _?(IntersectingQ[test,

NestList[nextNumber, #, 10]] &)]) &, candidates,

{{out}}

Note, here only 10 iterations were done for comparison. While reducing the number of

iterations is clearly effective for intergers less than 10,000 this may not be sufficient

 

The number of related Lychrel numbers is:

{{out}}

<pre>244

</pre>

The Lycrel numbers that are also palindromes are:

{{out}}

<pre>{4994,8778,9999}

</pre>

 

{{works with|Free Pascal}}

I use an array of byte.The trick is to add first, so i don't need to create a reversed number and only have to sum up one half and than correct the carry, which is most time consuming.

The main intention was to get below 1min for 100e6 ;-)

 

{$IFDEF FPC}

{$R-}

user 0m48.579s

sys 0m0.012s

 

{{out}}

</pre>

 

use English;

use Const::Fast;

 

const my $iter_cutoff => 500;

 

for (my $n=1; $n<=$n_max; $n++) {

my @seq = lychrel_sequence($n);

@seq_dump = set_union(\@seq_dump, \@seq);

}

}

 

sub lychrel_sequence {

my $n = shift;

for (1 .. $iter_cutoff) {

}

}

 

 

sub has_overlap {

my ($a, $b) = @ARG;

my %h;

}

 

my ($a, $b) = @ARG;

my %h;

{{out}}

<pre>

</pre>

 

 

 

 

 

{{out}}

 

(let N (chop N)

(= N (reverse N)) ) )

(lychrel 10000)

 

 

{{out}}

=={{header|PowerShell}}==

{{works with|PowerShell|4}}

function Test-Palindrome ( [String]$String )

{

return $LychrelNumbers

}

$Upto = 10000

$IterationLimit = 500

"Number of palindrome Lychrel numbers: " + $LychrelNumbers.Palindromes.Count

" Palindrome Lychrel numbers: " + ( $LychrelNumbers.Palindromes -join ", " )

{{out}}

<pre>

</pre>

 

 

def add_reverse(num, max_iter=1000):

pals = [x for x in lychrel + l_related if x == reverse_int(x)]

print(' Number of Lychrel palindromes:', len(pals))

 

{{out}}

 

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.

 

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

print("%d Lychel seeds:"%len(seeds), seeds)

print("%d Lychel related" % len(related))

 

 

(require racket/splicing)

 

Palindromic Lychrel numbers: ~a~%

EOS

 

{{out}}

Palindromic Lychrel numbers: ((4994 (related)) (8778 (related)) (9999 (seed)))</pre>

 

parse arg high limit . /*obtain optional argument from the CL.*/

if high='' | high=="," then high= 10000 /*Not specified? Then use the default.*/

numeric digits limit % 2 /*ensure enough decimal digits for adds*/

T.= 0; @.= T.; #.=@.; w= length(high) /*W: is used for formatting numbers. */

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

rels= 0 /*# related numbers (so far)*/

do limit; z= z + reverse(z) /*add the reverse of Z ··· */

T._= 1 /*mark number as "related".*/

end /*a*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

5 Lychrel numbers: 196 879 1997 7059 9999

3 Lychrel palindromes: 4994 8778 9999

</pre>

 

=={{header|Ruby}}==

{{trans|Python}}

 

def add_reverse(num, max_iter=1000)

pals = (lychrel + l_related).select{|x| palindrome?(x)}.sort

puts " Number of Lychrel palindromes: #{pals.length}"

 

{{out}}

 

'''src/main.rs'''

use num::FromPrimitive;

use num::bigint::BigInt;

println!("Number of Lychrel palindromes: {}", palindrome_lychrels.len());

print_nums("Lychrel palindromes: ", &palindrome_lychrels);

 

{{out}}

=={{header|Scala}}==

Using a '''Map''' to prevent duplicate values in the Lychrel sequence when determining seeds.

 

val range = 1 to 10000

println( s"\tRelated Count: ${related.size}" )

println( s"\t Palindromes: (${lychrelPals.mkString(", ")})")

 

{{out}}

 

=={{header|Sidef}}==

lychrels = [],

palindromes = [],

say ("Number of Lychrel related numbers < 10_000: ", lychrels.len - seeds.len)

say (" Number of Lychrel palindromes < 10_000: ", palindromes.len)

{{out}}

<pre>

{{libheader|AttaSwift's BigInt}}

 

 

public struct Lychrel<T: ReversibleNumeric & CustomStringConvertible>: Sequence, IteratorProtocol {

print("Lychrel seeds found: \(seeds.sorted())")

print("Number of related Lychrel nums found: \(related.count)")

 

{{out}}

Lychrel palindromes found: [4994, 8778, 9999]</pre>

 

=={{header|Tcl}}==

 

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 <tt>$visited</tt> 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

 

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

}

}

 

 

{{out}}

Count of related numbers: 244

Palindromic Lychrel and related numbers: 4994 8778 9999</pre>

 

=={{header|zkl}}==

 

The Lychrel number chain is stored as a long string with '\0' separating each number, which we can then search to find relateds.

 

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

}

seeds.apply("get",0)

println("[1..10,000] contains ",lychrels.len()," Lychrel numbers.");

 

(n:=findSeeds(lychrels))

.println("<-- Lychrel seeds (%d) ==> %d related"

{{out}}

<pre>