How to resolve the algorithm Lychrel numbers step by step in the Julia programming language

Published on 22 June 2024 08:30 PM

How to resolve the algorithm Lychrel numbers step by step in the Julia programming language

Table of Contents

Problem Statement

The above recurrence relation when applied to most starting numbers n = 1, 2, ... terminates in a palindrome quite quickly.

If n0 = 12 we get And if n0 = 55 we get 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.

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

Show all output here.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Lychrel numbers step by step in the Julia programming language

This Julia code performs computations related to the Lychrel conjecture, which states that there does not exist a positive integer n such that n + reverse(n) eventually forms a palindrome (a number that reads the same backward and forward). The code calculates and prints the number of Lychrel seeds (numbers that create palindromes after some iterations), related numbers (numbers that reach palindromes through other numbers), and palindromes reached through the Lychrel process.

A brief overview of the code's functionality:

  1. The reverse() function reverses the digits of an integer and returns it as a BigInt.

  2. The lychrel() function takes a BigInt n and returns a tuple (is_lychrel, final_number). It checks if n is already stored in a cache dictionary. If it is, it returns the cached result. Otherwise, it calculates the reverse of n (r) and initializes a tuple rst with (true, n) to indicate that n has not yet reached a palindrome and has not been seen before. It enters a loop that iterates up to 500 times:

    • In each iteration, it adds r to n and recalculates r as the reverse of the new n.
    • If n becomes equal to r, it means a palindrome has been reached, and rst is updated to (false, big(0)).
    • If n is found in the cache dictionary, it means it has been seen before, and the cached result is returned.
    • Otherwise, n is added to a set seen to keep track of numbers that have been encountered during the loop.
  3. After the loop completes, the rst tuple is cached for all numbers in the seen set.

  4. The code iterates through integers from 1 to 10000 and applies the lychrel() function to each integer. It maintains three arrays:

    • seeds stores integers that create palindromes after some iterations (Lychrel seeds).
    • related stores integers that reach palindromes through other numbers (Lychrel related).
    • palin stores palindromes reached through the Lychrel process.
  5. The code prints the number of Lychrel seeds, the number of Lychrel related numbers, and the number of Lychrel palindromes along with their values.

Source code in the julia programming language

const cache = Dict{BigInt, Tuple{Bool, BigInt}}()

Base.reverse(n::Integer) = parse(BigInt, string(n) |> reverse)
function lychrel(n::BigInt)::Tuple{Bool, BigInt}
    if haskey(cache, n)
        return cache[n]
    end

    r = reverse(n)
    rst = (true, n)
    seen = Set{BigInt}()
    for i in 0:500
        n += r
        r = reverse(n)
        if n == r
            rst = (false, big(0))
            break
        end
        if haskey(cache, n)
            rst = cache[n]
            break
        end
        push!(seen, n)
    end

    for bi in seen
        cache[bi] = rst
    end
    return rst
end

seeds   = BigInt[]
related = BigInt[]
palin   = BigInt[]

for n in big.(1:10000)
    t = lychrel(n)
    if ! t[1]
        continue
    end
    if n == t[2]
        push!(seeds, n)
    else
        push!(related, n)
    end

    if n == t[2]
        push!(palin, t[2])
    end
end

println(length(seeds),   " lychrel seeds: ", join(seeds, ", "))
println(length(related), " lychrel related")
println(length(palin),   " lychrel palindromes: ", join(palin, ", "))


  

You may also check:How to resolve the algorithm Command-line arguments step by step in the Nu programming language
You may also check:How to resolve the algorithm Start from a main routine step by step in the Mathematica/Wolfram Language programming language
You may also check:How to resolve the algorithm Increment a numerical string step by step in the Ada programming language
You may also check:How to resolve the algorithm Boolean values step by step in the C# programming language
You may also check:How to resolve the algorithm Farey sequence step by step in the Gambas programming language