Lychrel numbers: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Picat}}: Added {{out}}) |
m (→{{header|Wren}}: Minor tidy) |
||
(4 intermediate revisions by 2 users not shown) | |||
Line 76:
{{trans|D}}
<
R BigInt(reversed(String(n)))
Line 118:
print(seeds.len‘ Lychrel seeds: ’seeds)
print(related.len‘ Lychrel related’)
print(palin.len‘ Lychrel palindromes: ’palin)</
{{out}}
Line 131:
<br>
Uses the associative array from the Associative array iteration task.
<
# number of additions to attempt before deciding the number is Lychrel #
Line 298:
OD;
print( ( newline ) )
</syntaxhighlight>
</lang>▼
{{out}}
<pre>
Line 307:
=={{header|AppleScript}}==
<
script o
property digits : missing value -- Digits of the current startNumber or a derived sum.
Line 439:
end task
task()</
{{output}}
<
5 seed Lychrels: 196, 879, 1997, 7059, 9999
244 related Lychrels
3 palindromic Lychrels: 4994, 8778, 9999"</
=={{header|BASIC}}==
Line 457:
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 '
Line 783:
END FUNCTION
</syntaxhighlight>
Output while running:
Line 815:
{{trans|D}}
{{libheader|GMP}}
<
#include <map>
#include <vector>
Line 882:
print_vector(palindromes);
return 0;
}</
{{out}}
Line 893:
=={{header|Clojure}}==
<
(require [clojure.string :as s])
(require [clojure.set :as set-op])
Line 968:
(println count-palindromes "Lychrel palindromes found:" palindrom-n))
)
</syntaxhighlight>
{{out}}
Line 979:
=={{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)))
Line 1,005:
Number of related found: ~D~%Palyndrome Lychrel numbers: ~D => ~a~%"
n max (length seeds) (nreverse (mapcar #'car seeds)) related (length palyndromes) (nreverse palyndromes)) ))
</syntaxhighlight>
{{out}}
Line 1,020:
=={{header|Crystal}}==
{{trans|Ruby}}
<
require "big"
Line 1,072:
pals = (lychrel + l_related).select{|x| palindrome?(x)}.sort
puts " Number of Lychrel palindromes: #{pals.size}"
puts " Lychrel palindromes: #{pals}"</
{{out}}
Line 1,086:
=={{header|D}}==
{{trans|Python}}
<
auto rev(in BigInt n) {
Line 1,136:
writeln(related.length, " Lychrel related");
writeln(palin.length, " Lychrel palindromes: ", palin);
}</
{{out}}
<pre>5 Lychrel seeds: [196, 879, 1997, 7059, 9999]
Line 1,160:
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...
<syntaxhighlight lang="fortran">
SUBROUTINE CROAK(GASP) !A dying message.
CHARACTER*(*) GASP !The message.
Line 1,552:
WRITE (6,*) "Unused STASH entries =",AVAILS(0)
END
</syntaxhighlight>
Output: edited to put twenty numbers per line and omit the (1:''n'') of the output from BIGWRITE...
Line 1,589:
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 1,682:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre> Testing numbers: 1 to 10000
Line 1,694:
=={{header|Go}}==
<
import (
Line 1,824:
fmt.Println("Number of Lychrel palindromes:", len(pals))
fmt.Println(" Lychrel palindromes:", pals)
}</
{{out}}
<pre>
Line 1,836:
=={{header|Haskell}}==
<
import Data.List
Line 1,885:
putStrLn $ show palindromicLychrel ++ " are palindromic Lychrel numbers."
putStrLn $ show lychrelSeeds ++ " are Lychrel seeds."
putStrLn $ "There are " ++ show relatedCount ++ " related Lychrel numbers."</
{{Out}}
<pre>
Line 1,898:
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:
<
989330226271793404132120335101444022368928728236373385750622261099268167362912850818170039990942038798808908830140199820181718948328173760873880172226156484473632718819962221534191534021132404387162721132989</
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):
<
249</
(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
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</
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
Line 1,937:
788 1675 7436 13783 52514 94039 187088 1067869 10755470 18211171
790 887 1675 7436 13783 52514 94039 187088 1067869 10755470
879 1857 9438 17787 96558 182127 903408 1707717 8884788 17759676</
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
196 879 1997 7059 9999</
And, with that, we can find the count of "just related" lychrel numbers:
<
244</
And, finally, which of the (true or related) lychrel numbers were themselves palindromes?
<
4994 8778 9999</
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
Line 1,971:
244
(#~(=revdig))L
4994 8778 9999</
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.
Line 1,978:
Translation of [[Lychrel_numbers#Python|Python]] via [[Lychrel_numbers#D|D]]
{{works with|Java|8}}
<
import java.util.*;
Line 2,059:
System.out.printf("%d Lychrel palindromes: %s%n", palin.size(), palin);
}
}</
<pre>5 Lychrel seeds: [196, 879, 1997, 7059, 9999]
Line 2,066:
=={{header|jq}}==
<
# non-negative integers represented as decimal strings:
def add(num1;num2):
Line 2,129:
end
end ) ;
</syntaxhighlight>
'''The task'''
<
| {seed, palindromic_seed, related: (.related | length) }</
'''Output'''
Line 2,155:
{{works with|Julia|1.3}}
<
Base.reverse(n::Integer) = parse(BigInt, string(n) |> reverse)
Line 2,208:
println(length(seeds), " lychrel seeds: ", join(seeds, ", "))
println(length(related), " lychrel related")
println(length(palin), " lychrel palindromes: ", join(palin, ", "))</
{{out}}
Line 2,216:
=={{header|Kotlin}}==
<
import java.math.BigInteger
Line 2,277:
println("\nThere are ${palindromes.size} palindromic Lychrel numbers, namely")
println(palindromes)
}</
{{out}}
Line 2,295:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
A few convenient functions:
<
Block[{digits = IntegerDigits[n]}, digits == Reverse@digits]
Line 2,303:
palindromeQ@
Catch[Nest[If[palindromeQ[#], Throw[#], nextNumber[#]] &,
nextNumber[n], 500]]</
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];
Line 2,314:
Rest[#], _?(IntersectingQ[test,
NestList[nextNumber, #, 10]] &)]) &, candidates,
Length@# > 0 &]; seeds = Flatten@seeds</
{{out}}
<pre>{196,879,1997,7059,9999}</pre>
Line 2,322:
The number of related Lychrel numbers is:
<syntaxhighlight lang
{{out}}
<pre>244
</pre>
The Lycrel numbers that are also palindromes are:
<
{{out}}
<pre>{4994,8778,9999}
Line 2,337:
The program runs in 20-30 ms and there is probably still some room for optimizations.
<
type
Line 2,468:
echo "These candidate seed Lychrel numbers are: ", cand.seeds
echo &"Found {cand.relatedCount(4)} candidate related Lychrel numbers between 1 and 10000."
echo "Palindromic candidate Lychrel numbers between 1 and 10000 are: ", cand.palindromicLychrel(4)</
{{out}}
Line 2,484:
The main intention was to get below 1min for 100e6 ;-)
<
{$IFDEF FPC}
{$R-}
Line 2,780:
user 0m48.579s
sys 0m0.012s
}</
{{out}}
Line 2,793:
=={{header|Perl}}==
<
use warnings;
use English;
Line 2,844:
$h{$_}++ for @{$a}, @{$b};
keys %h;
}</
{{out}}
<pre> Number of seed Lychrels <= 10000: 5
Line 2,852:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">iterations</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">500</span><span style="color: #0000FF;">,</span>
Line 2,911:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"related lychrel: %d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">related</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d lychrel palindromes: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">palin</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">palin</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">", "</span><span style="color: #0000FF;">)})</span>
<!--</
{{out}}
Completes in under a second on desktop/Phix, but takes about 10s under pwa/p2js
Line 2,921:
=={{header|Picat}}==
<
Limit = 500,
Lychrel = [],
Line 2,967:
Seed = Seed1,
% The check: have we found a Lyncrel number
(OldHit == true ; Found == false).</
{{out}}
Line 2,977:
=={{header|PicoLisp}}==
<
(let N (chop N)
(= N (reverse N)) ) )
Line 3,031:
(lychrel 10000)
(bye)</
{{out}}
Line 3,045:
=={{header|PowerShell}}==
{{works with|PowerShell|4}}
<syntaxhighlight lang="powershell">
function Test-Palindrome ( [String]$String )
{
Line 3,148:
return $LychrelNumbers
}
</syntaxhighlight>
<syntaxhighlight lang="powershell">
$Upto = 10000
$IterationLimit = 500
Line 3,160:
"Number of palindrome Lychrel numbers: " + $LychrelNumbers.Palindromes.Count
" Palindrome Lychrel numbers: " + ( $LychrelNumbers.Palindromes -join ", " )
</syntaxhighlight>
{{out}}
<pre>
Line 3,174:
{{trans|D}}
{{works with|SWI Prolog}}
<
reverse_number(Number, 0, Rev).
Line 3,230:
main:-
lychrel(10000).</
{{out}}
Line 3,241:
=={{header|Python}}==
<
def add_reverse(num, max_iter=1000):
Line 3,288:
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))</
{{out}}
Line 3,299:
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])
Line 3,332:
print("%d Lychel seeds:"%len(seeds), seeds)
print("%d Lychel related" % len(related))
print("%d Lychel palindromes:" % len(palin), palin)</
=={{header|R}}==
<
library(gmp)
library(magrittr)
Line 3,407:
cat("Number of palindromic Lychrel numbers:",length(palindrome_lychrel),"\n")
cat("Palindromic Lychrel numbers:",palindrome_lychrel,"\n")
</syntaxhighlight>
{{out}}
<pre>
Line 3,421:
=={{header|Racket}}==
<
(require racket/splicing)
Line 3,480:
Palindromic Lychrel numbers: ~a~%
EOS
(reverse seeds/r) (length seeds/r) n-relateds (reverse palindromes/r)))</
{{out}}
Line 3,491:
{{works with|Rakudo|2018.03}}
<syntaxhighlight lang="raku"
my @seeds;
my @palindromes;
Line 3,536:
say "Number of Lychrel related numbers < $limit: ", +$count - @seeds;
say " Number of Lychrel palindromes < $limit: ", +@palindromes;
say " Lychrel palindromes < $limit: ", join ", ", @palindromes;</
{{out}}
Line 3,546:
=={{header|REXX}}==
<
parse arg high limit . /*obtain optional argument from the CL.*/
if high='' | high=="," then high= 10000 /*Not specified? Then use the default.*/
Line 3,581:
T._= 1 /*mark number as "related".*/
end /*a*/
return</
{{out|output|text= when using the default inputs:}}
<pre>
Line 3,590:
3 Lychrel palindromes: 4994 8778 9999
</pre>
=={{header|RPL}}==
{{works with|HP|49}}
« 0
'''WHILE''' OVER '''REPEAT''' 10 * SWAP 10 IDIV2 ROT + '''END'''
NIP
» '<span style="color:blue">IREVERSE</span>' STO
« { } DUP DUP2 500 0 → seeds related current palych stop counts
« 1 10000 '''FOR''' n
1 CF { } 'current' STO <span style="color:grey"> @ flag 1 set = n is not a Lychrel seed</span>
n DUP <span style="color:blue">IREVERSE</span>
'''IF''' DUP2 == '''THEN''' 2 SF '''ELSE''' 2 CF '''END''' <span style="color:grey">@ flag 2 set = n is palindromic</span>
1 stop '''FOR''' j
+ 'current' OVER STO+
'''IF''' related OVER POS '''THEN'''
'related' current STO+ 'counts' (0,1) STO+
'''IF''' 2 FS? '''THEN''' 'palych' n STO+ '''END'''
1 SF stop 'j' STO
'''END'''
DUP <span style="color:blue">IREVERSE</span>
'''IF''' DUP2 == '''THEN''' 1 SF stop 'j' STO '''END'''
'''NEXT''' DROP2
'''IF''' 1 FC? '''THEN'''
'related' current STO+ 'counts' 1 STO+ 'seeds' n STO+
'''IF''' 2 FS? '''THEN''' 'palych' n STO+ '''END'''
'''END'''
'''NEXT'''
seeds counts palych
» » '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
3: {196 879 1997 7059 9999}
2: (5.,244.)
1: {4994 8778 9999}
Results are identical when the loop limit is set at 50 instead of 500.
=={{header|Ruby}}==
{{trans|Python}}
<
def add_reverse(num, max_iter=1000)
Line 3,642 ⟶ 3,679:
pals = (lychrel + l_related).select{|x| palindrome?(x)}.sort
puts " Number of Lychrel palindromes: #{pals.length}"
puts " Lychrel palindromes: #{pals}"</
{{out}}
Line 3,667 ⟶ 3,704:
'''src/main.rs'''
<
use num::FromPrimitive;
use num::bigint::BigInt;
Line 3,784 ⟶ 3,821:
println!("Number of Lychrel palindromes: {}", palindrome_lychrels.len());
print_nums("Lychrel palindromes: ", &palindrome_lychrels);
}</
{{out}}
Line 3,796 ⟶ 3,833:
=={{header|Scala}}==
Using a '''Map''' to prevent duplicate values in the Lychrel sequence when determining seeds.
<
val range = 1 to 10000
Line 3,855 ⟶ 3,892:
println( s"\tRelated Count: ${related.size}" )
println( s"\t Palindromes: (${lychrelPals.mkString(", ")})")
}</
{{out}}
Line 3,868 ⟶ 3,905:
=={{header|Sidef}}==
{{trans|Raku}}
<
lychrels = [],
palindromes = [],
Line 3,913 ⟶ 3,950:
say ("Number of Lychrel related numbers < 10_000: ", lychrels.len - seeds.len)
say (" Number of Lychrel palindromes < 10_000: ", palindromes.len)
say (" Lychrel palindromes < 10_000: ", palindromes.join(', '))</
{{out}}
<pre>
Line 3,927 ⟶ 3,964:
{{libheader|AttaSwift's BigInt}}
<
public struct Lychrel<T: ReversibleNumeric & CustomStringConvertible>: Sequence, IteratorProtocol {
Line 4,025 ⟶ 4,062:
print("Lychrel seeds found: \(seeds.sorted())")
print("Number of related Lychrel nums found: \(related.count)")
print("Lychrel palindromes found: \(seeds.union(related).filter(isPalindrome).sorted())")</
{{out}}
Line 4,041 ⟶ 4,078:
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]}
}
Line 4,093 ⟶ 4,130:
}
lychrels</
{{out}}
Line 4,107 ⟶ 4,144:
{{libheader|Wren-big}}
{{libheader|Wren-set}}
<
import "./set" for Set
var iterations = 500
Line 4,169 ⟶ 4,206:
}
System.print("\nThere are %(palindromes.count) palindromic Lychrel numbers, namely:")
System.print(palindromes)</
{{out}}
Line 4,189 ⟶ 4,226:
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
Line 4,214 ⟶ 4,251:
}
seeds.apply("get",0)
}</
<
println("[1..10,000] contains ",lychrels.len()," Lychrel numbers.");
Line 4,223 ⟶ 4,260:
(n:=findSeeds(lychrels))
.println("<-- Lychrel seeds (%d) ==> %d related"
.fmt(n.len(),lychrels.len() - n.len()));</
{{out}}
<pre>
|