How to resolve the algorithm Primes - allocate descendants to their ancestors step by step in the Haskell programming language

Published on 7 June 2024 03:52 AM
#Haskell

How to resolve the algorithm Primes - allocate descendants to their ancestors step by step in the Haskell programming language

Table of Contents

Problem Statement

The concept, is to add the decomposition into prime factors of a number to get its 'ancestors'.

The objective is to demonstrate that the choice of the algorithm can be crucial in term of performance. This solution could be compared to the solution that would use the decomposition into primes for all the numbers between 1 and 333.

The problem is to list, for a delimited set of ancestors (from 1 to 99) :

  • the total of their own ancestors (LEVEL),
  • their own ancestors (ANCESTORS),
  • the total of the direct descendants (DESCENDANTS),
  • all the direct descendants.

You only have to consider the prime factors < 100. A grand total of the descendants has to be printed at the end of the list. The task should be accomplished in a reasonable time-frame.

Example : The list layout and the output for Parent [46] : Some figures :

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Primes - allocate descendants to their ancestors step by step in the Haskell programming language

This Haskell code defines functions to find ancestors and descendants of numbers, primarily regarding their prime factorization. Here's a breakdown:

Memoization Utilities:

  • Memo and Memo2 are data types used for memoization, storing values for later reuse to improve efficiency.
  • memo retrieves values from a memo table.
  • nats generates a sequence of natural numbers.
  • memoize and memoize2 wrap functions to memoize their results.

Part Product Function:

  • partProd computes the "part products" of a number. Given x and a prime p, it finds all possible products of primes less than or equal to p that sum to x. If p is prime, it recursively finds part products for x - p using p as a factor.

Descendants Function:

  • descendants finds the "descendants" of a number x. A descendant is a number whose part products include x. It sorts the list of descendants.

Ancestors Function:

  • ancestors finds the "ancestors" of a number z. An ancestor is a number whose descendants include z. It recursively searches for ancestors by finding descendants of numbers less than z.

Main Function:

  • main is the entry point.
  • task1 prints the ancestors and descendants of numbers from 1 to 15.
  • task2 prints the number of ancestors and descendants of 46 and 99.
  • task3 calculates and prints the total number of ancestors and descendants for all numbers up to 99.

In summary, this code efficiently computes the prime factorization of numbers and finds their ancestors (those whose descendants include them) and descendants (those whose part products include them) through memoization techniques.

Source code in the haskell programming language

{-# LANGUAGE DeriveFunctor #-}
import Data.Numbers.Primes (isPrime)
import Data.List

------------------------------------------------------------
-- memoization utilities

type Memo2 a = Memo (Memo a)

data Memo a = Node a (Memo a) (Memo a)
  deriving Functor

memo :: Integral a => Memo p -> a -> p
memo (Node a l r) n
  | n == 0 = a
  | odd n = memo l (n `div` 2)
  | otherwise = memo r (n `div` 2 - 1)

nats :: Integral a => Memo a
nats = Node 0 ((+1).(*2) <$> nats) ((*2).(+1) <$> nats)

memoize :: Integral a => (a -> b) -> (a -> b)
memoize f = memo (f <$> nats)

memoize2 :: (Integral a, Integral b) => (a -> b -> c) -> (a -> b -> c)
memoize2 f = memoize (memoize . f)

------------------------------------------------------------

partProd = memoize2 partProdM
  where
    partProdM x p
      | p == 0 = []
      | x == 0 = [1]
      | x < 0 = []
      | isPrime p = ((p *) <$> partProdM (x - p) p) ++
                    partProd x (p - 1)
      | otherwise = partProd x (p - 1)

descendants = memoize descendantsM
  where
    descendantsM x =
      if x == 4 then [] else sort (partProd x (x - 1))

ancestors = memoize ancestorsM
  where
    ancestorsM z = concat [ ancestors x ++ [x]
                          | x <- [z-1,z-2..1]
                          , z `elem` descendants x ]

main = do
  mapM_ (putStrLn . task1) [1..15]
  putStrLn (task2 46)
  putStrLn (task2 99)
  putStrLn task3
  where
    task1 n = show n ++
              "  ancestors:" ++ show (ancestors n) ++
              "  descendants:" ++ show (descendants n)
    task2 n = show n ++ " has " ++
              show (length (ancestors n)) ++ " ancestors, " ++
              show (length (descendants n)) ++ " descendants."
    task3 = "Total ancestors up to 99: " ++
            show (sum $ length . ancestors <$> [1..99]) ++
            "\nTotal descendants up to 99: " ++
            show (sum $ length . descendants <$> [1..99])

You may also check:How to resolve the algorithm XML/Input step by step in the XPL0 programming language
You may also check:How to resolve the algorithm Call a function in a shared library step by step in the Ursala programming language
You may also check:How to resolve the algorithm HTTP step by step in the TSE SAL programming language
You may also check:How to resolve the algorithm Hello world/Text step by step in the XPath programming language
You may also check:How to resolve the algorithm Levenshtein distance step by step in the Tcl programming language