How to resolve the algorithm Recaman's sequence step by step in the JavaScript programming language
How to resolve the algorithm Recaman's sequence step by step in the JavaScript programming language
Table of Contents
Problem Statement
The Recamán's sequence generates Natural numbers. Starting from a(0)=0, the n'th term a(n), where n>0, is the previous term minus n i.e a(n) = a(n-1) - n but only if this is both positive and has not been previousely generated. If the conditions don't hold then a(n) = a(n-1) + n.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Recaman's sequence step by step in the JavaScript programming language
This code implements the Recaman's sequence in Javascript programming language. The sequence start with 0 and the next term is obtained subtracting the previous term from the last term of the sequence, if the result is positive and not already in the sequence, otherwise adding the previous term. The main function
const main = () => {
console.log(
'First 15 Recaman:\n' +
recamanUpto(i => 15 === i)
);
console.log(
'\n\nFirst duplicated Recaman:\n' +
last(recamanUpto(
(_, set, rs) => set.size !== rs.length
))
);
const setK = new Set(enumFromTo(0, 1000));
console.log(
'\n\nNumber of Recaman terms needed to generate' +
'\nall integers from [0..1000]:\n' +
(recamanUpto(
(_, setR) => isSubSetOf(setK, setR)
).length - 1)
);
};
prints the first 15 terms of the Recaman sequence, the first duplicated term and the number of terms needed to generate all integers from 0 to 1000.
To generate the sequence the function recamanUpto is used, which takes a predicate function as input and returns a list of integers.
The predicate function is used to stop the generation of the sequence when a certain condition is met.
In the first call to recamanUpto, the predicate function checks if the length of the sequence is 15.
In the second call, the predicate function checks if there is a duplicated term in the sequence.
In the third call, the predicate function checks if all integers from 0 to 1000 are present in the sequence.
The function nextR is used to generate the next term of the sequence.
The function enumFromTo generates a list of integers from a starting value to an ending value.
The function isSubSetOf checks if a set is a subset of another set.
The function iterateUntil generates a list of values by applying a function to a starting value until a predicate function is satisfied.
The function last returns the last element of a list.
Source code in the javascript programming language
(() => {
const main = () => {
console.log(
'First 15 Recaman:\n' +
recamanUpto(i => 15 === i)
);
console.log(
'\n\nFirst duplicated Recaman:\n' +
last(recamanUpto(
(_, set, rs) => set.size !== rs.length
))
);
const setK = new Set(enumFromTo(0, 1000));
console.log(
'\n\nNumber of Recaman terms needed to generate' +
'\nall integers from [0..1000]:\n' +
(recamanUpto(
(_, setR) => isSubSetOf(setK, setR)
).length - 1)
);
};
// RECAMAN --------------------------------------------
// recamanUpto :: (Int -> Set Int > [Int] -> Bool) -> [Int]
const recamanUpto = p => {
let
i = 1,
r = 0, // First term of series
rs = [r];
const seen = new Set(rs);
while (!p(i, seen, rs)) {
r = nextR(seen, i, r);
seen.add(r);
rs.push(r);
i++;
}
return rs;
}
// Next Recaman number.
// nextR :: Set Int -> Int -> Int
const nextR = (seen, i, n) => {
const back = n - i;
return (0 > back || seen.has(back)) ? (
n + i
) : back;
};
// GENERIC --------------------------------------------
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = (m, n) =>
m <= n ? iterateUntil(
x => n <= x,
x => 1 + x,
m
) : [];
// isSubsetOf :: Ord a => Set a -> Set a -> Bool
const isSubSetOf = (a, b) => {
for (let x of a) {
if (!b.has(x)) return false;
}
return true;
};
// iterateUntil :: (a -> Bool) -> (a -> a) -> a -> [a]
const iterateUntil = (p, f, x) => {
const vs = [x];
let h = x;
while (!p(h))(h = f(h), vs.push(h));
return vs;
};
// last :: [a] -> a
const last = xs =>
0 < xs.length ? xs.slice(-1)[0] : undefined;
// MAIN ------------------------------------------------
return main();
})();
You may also check:How to resolve the algorithm Caesar cipher step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Miller–Rabin primality test step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Substring/Top and tail step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Elementary cellular automaton step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Guess the number step by step in the JavaScript programming language