Sequence: smallest number with exactly n divisors: Difference between revisions
Sequence: smallest number with exactly n divisors (view source)
Revision as of 15:12, 10 April 2020
, 4 years ago→{{header|JavaScript}}: Added a (functionally composed) JS draft.
m (→{{header|Haskell}}: Pruned a little noise) |
(→{{header|JavaScript}}: Added a (functionally composed) JS draft.) |
||
Line 332:
{{Out}}
<pre>[1,2,4,6,16,12,64,24,36,48,1024,60,4096,192,144]</pre>
=={{header|JavaScript}}==
Defining a generator in terms of re-usable generic functions, and taking the first 15 terms:
<lang JavaScript>(() => {
'use strict';
// a005179 :: () -> [Int]
const a005179 = () =>
fmapGen(
n => find(
compose(
eq(n),
succ,
length,
properDivisors
)
)(enumFrom(1)).Just
)(enumFrom(1));
// ------------------------TEST------------------------
// main :: IO ()
const main = () =>
console.log(
take(15)(
a005179()
)
);
// [1,2,4,6,16,12,64,24,36,48,1024,60,4096,192,144]
// -----------------GENERIC FUNCTIONS------------------
// Just :: a -> Maybe a
const Just = x => ({
type: 'Maybe',
Nothing: false,
Just: x
});
// Nothing :: Maybe a
const Nothing = () => ({
type: 'Maybe',
Nothing: true,
});
// Tuple (,) :: a -> b -> (a, b)
const Tuple = a =>
b => ({
type: 'Tuple',
'0': a,
'1': b,
length: 2
});
// compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
const compose = (...fs) =>
fs.reduce(
(f, g) => x => f(g(x)),
x => x
);
// enumFrom :: Enum a => a -> [a]
function* enumFrom(x) {
// A non-finite succession of enumerable
// values, starting with the value x.
let v = x;
while (true) {
yield v;
v = succ(v);
}
};
// eq (==) :: Eq a => a -> a -> Bool
const eq = a =>
// True when a and b are equivalent in the terms
// defined below for their shared data type.
b => a === b;
// find :: (a -> Bool) -> Gen [a] -> Maybe a
const find = p => xs => {
const mb = until(tpl => {
const nxt = tpl[0];
return nxt.done || p(nxt.value);
})(
tpl => Tuple(tpl[1].next())(
tpl[1]
)
)(Tuple(xs.next())(xs))[0];
return mb.done ? (
Nothing()
) : Just(mb.value);
}
// fmapGen <$> :: (a -> b) -> Gen [a] -> Gen [b]
const fmapGen = f =>
function*(gen) {
let v = take(1)(gen);
while (0 < v.length) {
yield(f(v[0]))
v = take(1)(gen)
}
};
// group :: [a] -> [[a]]
const group = xs => {
// A list of lists, each containing only equal elements,
// such that the concatenation of these lists is xs.
const go = xs =>
0 < xs.length ? (() => {
const
h = xs[0],
i = xs.findIndex(x => h !== x);
return i !== -1 ? (
[xs.slice(0, i)].concat(go(xs.slice(i)))
) : [xs];
})() : [];
return go(xs);
};
// length :: [a] -> Int
const length = xs =>
// Returns Infinity over objects without finite
// length. This enables zip and zipWith to choose
// the shorter argument when one is non-finite,
// like cycle, repeat etc
(Array.isArray(xs) || 'string' === typeof xs) ? (
xs.length
) : Infinity;
// liftA2List :: (a -> b -> c) -> [a] -> [b] -> [c]
const liftA2List = f => xs => ys =>
// The binary operator f lifted to a function over two
// lists. f applied to each pair of arguments in the
// cartesian product of xs and ys.
xs.flatMap(
x => ys.map(f(x))
);
// mul (*) :: Num a => a -> a -> a
const mul = a => b => a * b;
// properDivisors :: Int -> [Int]
const properDivisors = n =>
// The ordered divisors of n,
// excluding n itself.
1 < n ? (
sort(group(primeFactors(n)).reduce(
(a, g) => liftA2List(mul)(a)(
scanl(mul)([1])(g)
),
[1]
)).slice(0, -1)
) : [];
// primeFactors :: Int -> [Int]
const primeFactors = n => {
// A list of the prime factors of n.
const
go = x => {
const
root = Math.floor(Math.sqrt(x)),
m = until(
([q, _]) => (root < q) || (0 === (x % q))
)(
([_, r]) => [step(r), 1 + r]
)(
[0 === x % 2 ? 2 : 3, 1]
)[0];
return m > root ? (
[x]
) : ([m].concat(go(Math.floor(x / m))));
},
step = x => 1 + (x << 2) - ((x >> 1) << 1);
return go(n);
};
// scanl :: (b -> a -> b) -> b -> [a] -> [b]
const scanl = f => startValue => xs =>
xs.reduce((a, x) => {
const v = f(a[0])(x);
return Tuple(v)(a[1].concat(v));
}, Tuple(startValue)([startValue]))[1];
// sort :: Ord a => [a] -> [a]
const sort = xs => xs.slice()
.sort((a, b) => a < b ? -1 : (a > b ? 1 : 0));
// succ :: Enum a => a -> a
const succ = x =>
1 + x;
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = n =>
// The first n elements of a list,
// string of characters, or stream.
xs => 'GeneratorFunction' !== xs
.constructor.constructor.name ? (
xs.slice(0, n)
) : [].concat.apply([], Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}));
// until :: (a -> Bool) -> (a -> a) -> a -> a
const until = p => f => x => {
let v = x;
while (!p(v)) v = f(v);
return v;
};
// MAIN ---
return main();
})();</lang>
{{Out}}
<pre>[1,2,4,6,16,12,64,24,36,48,1024,60,4096,192,144]</pre>
=={{header|J}}==
| |||