Step by Step solution about How to resolve the algorithm Mian-Chowla sequence step by step in the Haskell programming language

Module Imports

import Data.Set (Set, fromList, insert, member)

This line imports the Data.Set module from the Haskell standard library, which provides data structures and functions for working with sets.

Main Function

mianChowlas :: Int -> [Int]

This is the main function that generates the Mian-Chowla sequence. It takes an integer n as input and returns a list of n integers in the sequence.

Sequence Generation

The main function uses a recursive function called iterate to generate the Mian-Chowla sequence. The iterate function takes a starting value and a function and applies the function to the starting value repeatedly, building a list of the results.

In this case, the starting value is a tuple of two sets: (fromList [2], [1]). The first set contains the integer 2, and the second set contains the integer 1.

The function applied to the starting value is nextMC, which is defined below. nextMC takes a tuple of sets as input and returns a new tuple of sets.

nextMC Function

nextMC :: (Set Int, [Int]) -> (Set Int, [Int])

The nextMC function takes two sets and a list as input:

• sumSet: A set of integers that are the sum of two or more elements in the sequence.
• mcs: A list of the Mian-Chowla sequence numbers generated so far.
• n: The current number in the sequence.

The nextMC function first calculates the next number in the sequence by finding the smallest integer m that is not already in the sumSet and is greater than or equal to n. It then adds m to the mcs list and inserts m and all its multiples into the sumSet.

Validity Check

The nextMC function uses a helper function called valid to determine if the next number in the sequence is valid. A number is valid if it is not the sum of any two or more numbers in the mcs list.

Iteration

The iterate function is called with the starting value and the nextMC function. The resulting list of tuples is reversed, and the second element of each tuple (the updated mcs list) is taken as the output.

Subtract 1

The final result is reduced by 1 to account for the fact that the Mian-Chowla sequence starts with 1 instead of 0.

Testing

The main function prints out the first 30 terms of the Mian-Chowla sequence and the terms from 91 to 100.

import Data.Set (Set, fromList, insert, member)

------------------- MIAN-CHOWLA SEQUENCE -----------------
mianChowlas :: Int -> [Int]
mianChowlas =
  reverse . snd . (iterate nextMC (fromList [2], [1]) !!) . subtract 1

nextMC :: (Set Int, [Int]) -> (Set Int, [Int])
nextMC (sumSet, mcs@(n:_)) =
  (foldr insert sumSet ((2 * m) : fmap (m +) mcs), m : mcs)
  where
    valid x = not $ any (flip member sumSet . (x +)) mcs
    m = until valid succ n

--------------------------- TEST -------------------------
main :: IO ()
main =
  (putStrLn . unlines)
    [ "First 30 terms of the Mian-Chowla series:"
    , show (mianChowlas 30)
    , []
    , "Terms 91 to 100 of the Mian-Chowla series:"
    , show $ drop 90 (mianChowlas 100)
    ]