JavaScript: Math, 1–40

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24const a = 17;
const b = 5;

const sum = a + b;
const difference = a - b;
const product = a * b;
const quotient = a / b;          // 3.4 — division never truncates in JavaScript
const remainder = a % b;         // what is left after 3 whole fives
const power = a ** 2;

// Precedence: ** first, then * / %, then + -.
const mixed = 2 + 3 * 4 ** 2;         // 4**2 = 16, 3*16 = 48, 48+2 = 50
const bracketed = (2 + 3) * 4 ** 2;   // 5*16 = 80

// ** associates to the right; everything else here goes left to right.
const tower = 2 ** 3 ** 2;            // 2 ** 9
const grouped = (2 ** 3) ** 2;        // 8 ** 2

console.log('sum, difference, product :', sum, difference, product);
console.log('quotient, remainder      :', quotient, remainder);
console.log('17 squared               :', power);
console.log('2 + 3 * 4 ** 2           :', mixed);
console.log('(2 + 3) * 4 ** 2         :', bracketed);
console.log('2 ** 3 ** 2              :', tower, 'not', grouped);

1
2
3
4
5
6
7
8const gap = (a, b) => Math.abs(a - b);

console.log('abs(-5)      :', Math.abs(-5));
console.log('abs(5)       :', Math.abs(5));
console.log('gap(3, 10)   :', gap(3, 10), 'and the other way round:', gap(10, 3));
console.log("abs('-3')    :", Math.abs('-3'), '<- coerced to a number first');
console.log("abs('twenty'):", Math.abs('twenty'));
console.log('abs(-0)      :', Math.abs(-0), 'is it exactly +0?', Object.is(Math.abs(-0), 0));

1
2
3
4
5
6
7
8
9
10
11console.log('sign(42)   :', Math.sign(42));
console.log('sign(-42)  :', Math.sign(-42));
console.log('sign(0)    :', Math.sign(0));
console.log('sign(-0)   :', Math.sign(-0), '<- printed as -0, and === 0 is true');
console.log('sign(NaN)  :', Math.sign(NaN));
console.log("sign('5')  :", Math.sign('5'), '<- coerced');
console.log('is it -0?  :', Object.is(Math.sign(-0), -0));
console.log('JSON sees  :', JSON.stringify(Math.sign(-0)), '<- which is why the check uses Object.is');

// sign and abs are complements: together they rebuild the number.
const rebuild = (n) => Math.sign(n) * Math.abs(n);

1
2
3
4
5
6
7
8
9
10
11
12
13const readings = [23, 41, 12, 38];

const clamp = (n, low, high) => Math.min(Math.max(n, low), high);

// Spread has an argument limit, so a very long array wants reduce instead.
const maxByReduce = (xs) => xs.reduce((m, n) => Math.max(m, n), -Infinity);

console.log('min      :', Math.min(...readings));
console.log('max      :', Math.max(...readings));
console.log('no args  :', Math.max(), 'and', Math.min(), '<- the identities');
console.log('with NaN :', Math.max(1, NaN, 3));
console.log('clamped  :', [clamp(5, 1, 10), clamp(-2, 1, 10), clamp(99, 1, 10)]);
console.log('by reduce:', maxByReduce(readings));

1
2
3
4
5
6
7
8
9
10
11
12const show = (n) => ({
  floor: Math.floor(n),
  ceil: Math.ceil(n),
  round: Math.round(n),
  trunc: Math.trunc(n),
});

console.log('2.7 ->', show(2.7));
console.log('2.4 ->', show(2.4));
console.log('2.5 ->', show(2.5), '<- a tie goes up');
console.log('2.1 ->', show(2.1));
console.log('3   ->', show(3), '<- a whole number is untouched by all four');

1
2
3
4
5
6
7
8
9
10
11
12
13const show = (n) => ({
  floor: Math.floor(n),
  ceil: Math.ceil(n),
  round: Math.round(n),
  trunc: Math.trunc(n),
});

console.log('-1.7 ->', show(-1.7));
console.log('-1.5 ->', show(-1.5), '<- the tie went towards zero');
console.log('-2.5 ->', show(-2.5));
console.log('-0.5 ->', show(-0.5), '<- round gave -0');
console.log('round(-0.5) is -0?', Object.is(Math.round(-0.5), -0));
console.log('and trunc(-0.1) is -0 as well:', Object.is(Math.trunc(-0.1), -0));

1
2
3
4
5
6
7
8
9
10
11
12
13
14const round = (n, places = 0) => {
  const factor = 10 ** places;
  return Math.round(n * factor) / factor;
};

const toNearest = (n, step) => Math.round(n / step) * step;

console.log('round(3.14159, 2) :', round(3.14159, 2));
console.log('round(2.5)        :', round(2.5));
console.log('round(-3.14159, 3):', round(-3.14159, 3));
console.log('round(1.005, 2)   :', round(1.005, 2), '<- expected 1.01');
console.log('why: 1.005 * 100  =', 1.005 * 100, '<- just under 100.5');
console.log('nearest 50 of 1234:', toNearest(1234, 50));
console.log('nearest 1000 naira:', toNearest(1499999, 1000));

1
2
3
4
5
6
7
8
9
10const price = 3.14159;

console.log('toFixed(2)        :', price.toFixed(2), 'typeof', typeof price.toFixed(2));
console.log('back to a number  :', Number(price.toFixed(2)));
console.log('(5).toFixed(2)    :', (5).toFixed(2), '<- padded');
console.log('(0.615).toFixed(2):', (0.615).toFixed(2), '<- not 0.62');
console.log('the stored value  :', (0.615).toFixed(20));
console.log('toPrecision(6)    :', (1234.5678).toPrecision(6));
console.log('toPrecision(2)    :', (123456).toPrecision(2), '<- exponential');
console.log('adding two strings:', (1.5).toFixed(1) + (2.5).toFixed(1));

1
2
3
4
5
6
7
8const roundHalfAway = (n) => Math.sign(n) * Math.round(Math.abs(n));

console.log('2.5  ->', roundHalfAway(2.5), ' Math.round says', Math.round(2.5));
console.log('-2.5 ->', roundHalfAway(-2.5), 'Math.round says', Math.round(-2.5));
console.log('-0.5 ->', roundHalfAway(-0.5), 'Math.round says', Math.round(-0.5));
console.log('-1.4 ->', roundHalfAway(-1.4), 'and -1.6 ->', roundHalfAway(-1.6));
console.log('a refund of 150.5 kobo either way:', [roundHalfAway(150.5), roundHalfAway(-150.5)]);
console.log('toFixed(0) rounds the same way:', (2.5).toFixed(0), (-2.5).toFixed(0));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19function roundHalfEven(n) {
  const low = Math.floor(n);
  const fraction = n - low;
  if (fraction > 0.5) return low + 1;
  if (fraction < 0.5) return low;
  return low % 2 === 0 ? low : low + 1;      // an exact tie: take the even side
}

const halves = [0.5, 1.5, 2.5, 3.5];
const exact = halves.reduce((s, n) => s + n, 0);
const evenTotal = halves.reduce((s, n) => s + roundHalfEven(n), 0);
const roundTotal = halves.reduce((s, n) => s + Math.round(n), 0);

console.log('half to even :', halves.map(roundHalfEven));
console.log('Math.round   :', halves.map((n) => Math.round(n)));
console.log('exact total  :', exact);
console.log('even total   :', evenTotal, '<- unchanged');
console.log('round total  :', roundTotal, '<- two too many');
console.log('negatives    :', [-1.5, -2.5].map(roundHalfEven));

1
2
3
4
5
6console.log('0.1 + 0.2      :', 0.1 + 0.2);
console.log('=== 0.3        :', 0.1 + 0.2 === 0.3);
console.log('the difference :', 0.1 + 0.2 - 0.3);
console.log('0.1 really is  :', (0.1).toFixed(20));
console.log('0.5 really is  :', (0.5).toFixed(20), '<- exact, it is a power of two');
console.log('left to right  :', 0.1 + 0.2 + 0.3, 'against', 0.3 + 0.2 + 0.1);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17const close = (a, b, tol = 1e-9) => Math.abs(a - b) < tol;

const closeRel = (a, b, tol = 1e-9) =>
  Math.abs(a - b) <= tol * Math.max(Math.abs(a), Math.abs(b), 1);

// A thousand additions of a thousandth: the error is now wider than EPSILON.
let accumulated = 0;
for (let i = 0; i < 1000; i++) accumulated += 0.001;

console.log('EPSILON              :', Number.EPSILON);
console.log('1 + EPSILON === 1    :', 1 + Number.EPSILON === 1);
console.log('1 + EPSILON/2 === 1  :', 1 + Number.EPSILON / 2 === 1, '<- it vanished');
console.log('close(0.1+0.2, 0.3)  :', close(0.1 + 0.2, 0.3));
console.log('close(1e16, 1e16+2)  :', close(1e16, 1e16 + 2), '<- 2 apart, and adjacent doubles');
console.log('closeRel(1e16, +2)   :', closeRel(1e16, 1e16 + 2));
console.log('closeRel(1, 1.1)     :', closeRel(1, 1.1), '<- still refuses real differences');
console.log('1000 x 0.001         :', accumulated, 'off by', Math.abs(accumulated - 1));

1
2
3
4
5
6
7
8
9console.log('0.1 * 3        :', 0.1 * 3);
console.log('0.3 - 0.1      :', 0.3 - 0.1);
console.log('1.1 * 3        :', 1.1 * 3);
console.log('4.35 * 100     :', 4.35 * 100, '<- kobo, apparently');
console.log('0.07 * 100     :', 0.07 * 100, '<- 7% of 100');
console.log('0.1 + 0.7      :', 0.1 + 0.7);
console.log('times 10       :', (0.1 + 0.7) * 10);
console.log('floored        :', Math.floor((0.1 + 0.7) * 10), '<- the classic off-by-one');
console.log('rounded instead:', Math.round((0.1 + 0.7) * 10));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35let ten = 0;
for (let i = 0; i < 10; i++) ten += 0.1;

let hundred = 0;
for (let i = 0; i < 100; i++) hundred += 0.1;

// Fix one: count in integers, divide once.
const tenths = (count) => count / 10;

// Fix two: Kahan summation. `c` carries the low-order bits that were lost.
function kahan(xs) {
  let sum = 0;
  let c = 0;
  for (const x of xs) {
    const y = x - c;
    const t = sum + y;
    c = t - sum - y;
    sum = t;
  }
  return sum;
}

// A float loop counter that tests for equality may never stop, so this one is bounded.
const steps = (() => {
  let x = 0;
  let n = 0;
  while (x !== 1 && n < 20) { x += 0.1; n++; }
  return n;
})();

console.log('ten additions    :', ten, ' === 1?', ten === 1);
console.log('hundred additions:', hundred);
console.log('integers instead :', tenths(10), tenths(100));
console.log('kahan            :', kahan(new Array(10).fill(0.1)));
console.log('a while (x !== 1) loop ran', steps, 'times without ever hitting 1');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18const toKobo = (naira) => Math.round(naira * 100);
const naira = (kobo) => (kobo / 100).toFixed(2);

const prices = [19.99, 5.75, 3.4];
const inKobo = prices.map(toKobo);                 // [1999, 575, 340]
const subtotal = inKobo.reduce((a, b) => a + b, 0);
const vat = Math.round(subtotal * 0.075);          // 7.5%, to the nearest kobo
const total = subtotal + vat;

const floatTotal = prices.reduce((a, b) => a + b, 0);

console.log('prices     :', prices);
console.log('as kobo    :', inKobo);
console.log('subtotal   :', subtotal, 'kobo =', naira(subtotal));
console.log('VAT        :', vat, 'kobo');
console.log('total      :', total, 'kobo =', naira(total));
console.log('float total:', floatTotal, '<- and it should be 29.14');
console.log('a price times 100 direct:', 19.99 * 100);

1
2
3
4
5
6
7
8console.log('MAX_VALUE      :', Number.MAX_VALUE);
console.log('doubled        :', Number.MAX_VALUE * 2);
console.log('MIN_VALUE      :', Number.MIN_VALUE, '<- smallest positive, not most negative');
console.log('halved         :', Number.MIN_VALUE / 2, '<- gone');
console.log('2 ** 1023      :', 2 ** 1023);
console.log('2 ** 1024      :', 2 ** 1024);
console.log('through JSON   :', JSON.stringify({ big: Infinity, bad: NaN }));
console.log('Infinity - Infinity:', Infinity - Infinity);

1
2
3
4
5
6
7
8console.log('isInteger(5)      :', Number.isInteger(5));
console.log('isInteger(5.0)    :', Number.isInteger(5.0), '<- there is no separate float type');
console.log('isInteger(5.5)    :', Number.isInteger(5.5));
console.log("isInteger('5')    :", Number.isInteger('5'), '<- a string is not a number');
console.log("isNaN('abc')      :", isNaN('abc'), 'against Number.isNaN:', Number.isNaN('abc'));
console.log("isFinite('42')    :", isFinite('42'), 'against Number.isFinite:', Number.isFinite('42'));
console.log('NaN === NaN       :', NaN === NaN);
console.log('Object.is(NaN,NaN):', Object.is(NaN, NaN));

1
2
3
4
5
6
7
8
9
10const max = Number.MAX_SAFE_INTEGER;

console.log('MAX_SAFE_INTEGER :', max);
console.log('is 2 ** 53 - 1   :', max === 2 ** 53 - 1);
console.log('max + 1          :', max + 1);
console.log('max + 2          :', max + 2, '<- the same double');
console.log('2 ** 53 + 1      :', 2 ** 53 + 1, '<- did not move');
console.log('a 16-digit id    :', Number('9007199254740993'));
console.log('isSafeInteger    :', Number.isSafeInteger(2 ** 53 - 1), Number.isSafeInteger(2 ** 53));
console.log('isInteger(2**60) :', Number.isInteger(2 ** 60), '<- still whole, just not safe');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18const big = 2n ** 64n;

const mixed = (() => {
  try { return String(1n + 1); } catch (e) { return e.constructor.name; }
})();

const jsonRefused = (() => {
  try { return JSON.stringify({ big: 1n }); } catch (e) { return e.constructor.name; }
})();

console.log('2n ** 64n      :', big.toString());
console.log('typeof         :', typeof big);
console.log('exact past 2^53:', (2n ** 53n + 1n).toString());
console.log('as a Number    :', (2 ** 53) + 1, '<- did not move');
console.log('1n + 1         :', mixed);
console.log('7n / 2n        :', (7n / 2n).toString(), '<- truncated, no fraction exists');
console.log('JSON.stringify :', jsonRefused);
console.log('loose vs strict:', 10n == 10, 10n === 10);

1
2
3
4
5
6
7
8
9
10
11
12
13const inputs = ['42', '42abc', '0.9', '', '  12  ', '1e3'];

const table = inputs.map((s) => ({
  input: JSON.stringify(s),
  number: Number(s),
  parseInt: parseInt(s, 10),
  plus: +s,
}));

for (const row of table) console.log(row);

console.log('Number(null)      :', Number(null), 'Number(undefined):', Number(undefined));
console.log('Number(true)      :', Number(true), 'Number([])       :', Number([]));

1
2
3
4
5
6
7
8
9const mapped = ['10', '10', '10'].map(parseInt);   // radix 0, then 1, then 2

console.log("parseInt('101', 2) :", parseInt('101', 2));
console.log("parseInt('ff', 16) :", parseInt('ff', 16));
console.log("parseInt('0x1f')   :", parseInt('0x1f'), '<- prefix honoured with no radix');
console.log("parseInt('08')     :", parseInt('08'), '<- decimal, not octal');
console.log("parseInt('8', 8)   :", parseInt('8', 8), '<- 8 is not a base-8 digit');
console.log("parseInt('129', 8) :", parseInt('129', 8), "<- read '12', stopped at the 9");
console.log('map(parseInt)      :', mapped);

1
2
3
4
5
6
7
8
9const divide = (a, b) => ({ quotient: Math.trunc(a / b), remainder: a % b });

console.log('divide(17, 5)   :', divide(17, 5));
console.log('divide(-17, 5)  :', divide(-17, 5), '<- trunc, so -3 remainder -2');
console.log('rebuild         :', 5 * -3 + -2);
console.log('floor would give:', Math.floor(-17 / 5));
console.log('1 / 0           :', 1 / 0, ' -1 / 0:', -1 / 0, ' 0 / 0:', 0 / 0);
console.log('5 % 0           :', 5 % 0);
console.log('how many 40-seat buses for 145 passengers:', Math.ceil(145 / 40));

1
2
3
4
5
6
7console.log('7 % 3    :', 7 % 3);
console.log('-7 % 3   :', -7 % 3, '<- sign of the dividend');
console.log('7 % -3   :', 7 % -3, '<- divisor sign ignored');
console.log('-7 % -3  :', -7 % -3);
console.log('by definition:', -7 - Math.trunc(-7 / 3) * 3);
console.log('5.5 % 2  :', 5.5 % 2, '<- fractions are allowed');
console.log('wrapping an index backwards:', -1 % 5, '<- not 4');

1
2
3
4
5
6
7
8
9
10
11
12const mod = (n, m) => ((n % m) + m) % m;

const stops = ['Yaba', 'Surulere', 'Mushin', 'Oshodi', 'Ikeja'];
const step = (i, by) => stops[mod(i + by, stops.length)];

console.log('mod(7, 3)    :', mod(7, 3));
console.log('mod(-7, 3)   :', mod(-7, 3), '<- where % gives', -7 % 3);
console.log('mod(-1, 5)   :', mod(-1, 5));
console.log('clock        : 3 hours before 1 is', mod(1 - 3, 12));
console.log('26 hours on  :', mod(26, 24));
console.log('one stop back from Yaba:', step(0, -1));
console.log('mod(7, -3)   :', mod(7, -3), '<- follows the modulus sign');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16const divisibleBy = (n, d) => n % d === 0;

const label = (n) =>
  divisibleBy(n, 15) ? 'fizzbuzz'
  : divisibleBy(n, 3) ? 'fizz'
  : divisibleBy(n, 5) ? 'buzz'
  : String(n);

const labels = Array.from({ length: 15 }, (_, i) => label(i + 1));

console.log('15 by 3 and 5 :', divisibleBy(15, 3), divisibleBy(15, 5));
console.log('16 by either  :', divisibleBy(16, 3), divisibleBy(16, 5));
console.log('-9 by 3       :', divisibleBy(-9, 3));
console.log('7 by 0        :', divisibleBy(7, 0), '<- 7 % 0 is', 7 % 0);
console.log('labels        :', labels.join(' '));
console.log('digit-sum rule for 3 on 12345:', 12345 % 3 === 0, (1 + 2 + 3 + 4 + 5) % 3 === 0);

1
2
3
4
5
6
7
8
9
10const isEven = (n) => Number.isInteger(n) && n % 2 === 0;
const isOdd = (n) => Number.isInteger(n) && Math.abs(n % 2) === 1;

console.log('8, 7        :', isEven(8), isEven(7));
console.log('-7 odd?     :', isOdd(-7), 'because -7 % 2 is', -7 % 2);
console.log('0 even?     :', isEven(0));
console.log('8.5         :', isEven(8.5), isOdd(8.5), '<- neither');
console.log('8.5 & 1     :', 8.5 & 1, '<- truncated to 8 first, so it looks even');
console.log('big integer :', (2 ** 40 + 1) & 1, '<- parity survives 32-bit truncation');
console.log('1 to 4      :', [1, 2, 3, 4].map(isEven));

1
2
3
4
5
6
7
8console.log('2 ** 10        :', 2 ** 10, 'and Math.pow:', Math.pow(2, 10));
console.log('27 ** (1/3)    :', 27 ** (1 / 3), '<- a root');
console.log('2 ** -2        :', 2 ** -2, '<- a reciprocal');
console.log('anything ** 0  :', 0 ** 0, 5 ** 0);
console.log('2 ** 3 ** 2    :', 2 ** 3 ** 2, '<- right associative');
console.log('2 ** 1023      :', 2 ** 1023);
console.log('2 ** 1024      :', 2 ** 1024, '<- over the edge');
console.log('(-8) ** (1/3)  :', (-8) ** (1 / 3), '<- no real answer by this route');

1
2
3
4
5
6
7console.log('sqrt(144)     :', Math.sqrt(144));
console.log('sqrt(2)       :', Math.sqrt(2));
console.log('squared again :', Math.sqrt(2) ** 2, '<- not 2');
console.log('sqrt(-4)      :', Math.sqrt(-4));
console.log('cbrt(-27)     :', Math.cbrt(-27));
console.log('144 ** 0.5    :', 144 ** 0.5);
console.log('sqrt(0), sqrt(Infinity):', Math.sqrt(0), Math.sqrt(Infinity));

1
2
3
4
5
6
7
8
9
10
11
12
13
14function nthRoot(x, n) {
  if (x < 0 && Math.abs(n % 2) === 1) return -(Math.abs(x) ** (1 / n));
  return x ** (1 / n);
}

// Roots are rarely exact, so compare after rounding.
const round = (v, places = 10) => Math.round(v * 10 ** places) / 10 ** places;

console.log('nthRoot(27, 3)  :', nthRoot(27, 3));
console.log('nthRoot(81, 4)  :', nthRoot(81, 4));
console.log('nthRoot(-32, 5) :', nthRoot(-32, 5));
console.log('plain expression:', (-32) ** (1 / 5), '<- NaN');
console.log('nthRoot(-16, 4) :', nthRoot(-16, 4), '<- correctly no real answer');
console.log('nthRoot(1000, 3):', nthRoot(1000, 3), 'against Math.cbrt:', Math.cbrt(1000));

1
2
3
4
5
6
7
8
9
10const manual = (a, b) => Math.sqrt(a * a + b * b);

console.log('hypot(3, 4)      :', Math.hypot(3, 4));
console.log('hypot(2, 3, 6)   :', Math.hypot(2, 3, 6));
console.log('manual(3, 4)     :', manual(3, 4));
console.log('3e200 squared    :', 3e200 * 3e200, '<- overflowed');
console.log('manual(3e200, 4e200):', manual(3e200, 4e200));
console.log('hypot(3e200,4e200)  :', Math.hypot(3e200, 4e200), '<- should be 5e200');
console.log('hypot()          :', Math.hypot());
console.log('with an Infinity :', Math.hypot(Infinity, NaN));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40let divisions = 0;                 // a counter, so the saving is measurable

function isPrime(n) {
  if (!Number.isInteger(n) || n < 2) return false;
  if (n % 2 === 0) return n === 2;                 // 2 is prime, other evens are not
  for (let d = 3; d * d <= n; d += 2) {
    divisions++;
    if (n % d === 0) return false;
  }
  return true;
}

// The same question answered without the shortcut: every divisor up to n - 1.
const workIfNaive = (n) => {
  let c = 0;
  for (let d = 2; d < n; d++) {
    c++;
    if (n % d === 0) break;
  }
  return c;
};

const primesBelow30 = [];
for (let n = 0; n < 30; n++) if (isPrime(n)) primesBelow30.push(n);

divisions = 0;
const prime9973 = isPrime(9973);
const workToRoot = divisions;

divisions = 0;
const composite9409 = isPrime(9409);      // 97 * 97, so the only divisor sits on the root
const workTo9409 = divisions;

const oddsBelowRoot = (Math.floor(Math.sqrt(9973)) - 3) / 2 + 1;

console.log('primes below 30 :', primesBelow30);
console.log('9973 is prime   :', prime9973, 'after', workToRoot, 'divisions');
console.log('sqrt(9973)      :', Math.sqrt(9973));
console.log('9409 is prime   :', composite9409, 'settled after', workTo9409, 'divisions');
console.log('to n - 1 instead:', workIfNaive(9973), 'divisions');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30const markers = [];                  // which primes actually did any striking out

function sieve(limit) {
  if (limit < 2) return [];
  const composite = new Uint8Array(limit + 1);
  for (let p = 2; p * p <= limit; p++) {
    if (composite[p]) continue;        // p was struck out, so it is not prime
    if (limit === 50) markers.push(p);
    for (let m = p * p; m <= limit; m += p) composite[m] = 1;
  }
  const out = [];
  for (let n = 2; n <= limit; n++) if (!composite[n]) out.push(n);
  return out;
}

const isPrime = (n) => {
  if (n < 2) return false;
  if (n % 2 === 0) return n === 2;
  for (let d = 3; d * d <= n; d += 2) if (n % d === 0) return false;
  return true;
};

const to50 = sieve(50);
const to100000 = sieve(100000);
const counts = [100, 1000, 10000].map((n) => sieve(n).length);

console.log('primes to 50    :', to50);
console.log('markers used    :', markers, '<- nothing above sqrt(50)');
console.log('counts          :', counts);
console.log('primes below 1e5:', to100000.length, 'largest:', to100000.at(-1));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35function nthPrimeByCounting(n) {
  if (!Number.isInteger(n) || n < 1) return NaN;
  const isPrime = (m) => {
    if (m < 2) return false;
    if (m % 2 === 0) return m === 2;
    for (let d = 3; d * d <= m; d += 2) if (m % d === 0) return false;
    return true;
  };
  let seen = 0;
  for (let c = 2; ; c++) if (isPrime(c) && ++seen === n) return c;
}

// Rosser and Schoenfeld: p(n) < n * (ln n + ln ln n) for n >= 6.
const bound = (n) => (n < 6 ? 15 : Math.ceil(n * (Math.log(n) + Math.log(Math.log(n)))));

function nthPrimeBySieve(n) {
  const limit = bound(n);
  const composite = new Uint8Array(limit + 1);
  let seen = 0;
  for (let p = 2; p <= limit; p++) {
    if (composite[p]) continue;
    if (++seen === n) return p;
    for (let m = p * p; m <= limit; m += p) composite[m] = 1;
  }
  return NaN;                          // the bound was too small
}

const firstTen = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].map(nthPrimeByCounting);
const counted1000 = nthPrimeByCounting(1000);      // counted once, reused below
const sieved10001 = nthPrimeBySieve(10001);

console.log('first ten     :', firstTen);
console.log('1000th        :', counted1000, 'and by sieve:', nthPrimeBySieve(1000));
console.log('10001st       :', sieved10001, 'from a sieve of', bound(10001));
console.log('nthPrime(0)   :', nthPrimeByCounting(0));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30function factorise(n) {
  const out = [];
  for (let d = 2; d * d <= n; d++) {
    while (n % d === 0) {
      out.push(d);
      n /= d;                          // n shrinks, so the bound tightens as we go
    }
  }
  if (n > 1) out.push(n);              // the last cofactor is prime
  return out;
}

// The same information, one entry per distinct prime.
const exponents = (n) => {
  const groups = [];
  for (const p of factorise(n)) {
    const last = groups.at(-1);
    if (last && last[0] === p) last[1]++;
    else groups.push([p, 1]);
  }
  return groups;
};

const divisorCount = (n) => exponents(n).reduce((acc, [, e]) => acc * (e + 1), 1);

console.log('360        :', factorise(360));
console.log('as powers  :', exponents(360));
console.log('1000000    :', exponents(1000000));
console.log('MAX_SAFE   :', factorise(Number.MAX_SAFE_INTEGER));
console.log('a big one  :', factorise(600851475143));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27let iterations = 0;

function divisors(n) {
  if (!Number.isInteger(n) || n < 1) return [];
  const small = [];
  const large = [];
  for (let d = 1; d * d <= n; d++) {
    iterations++;
    if (n % d !== 0) continue;
    small.push(d);
    if (d !== n / d) large.push(n / d);      // skip the partner of a square root
  }
  return [...small, ...large.reverse()];
}

const oddCount = [];
for (let n = 1; n <= 50; n++) if (divisors(n).length % 2 === 1) oddCount.push(n);

iterations = 0;
const ofMillion = divisors(1000000);
const workForMillion = iterations;

console.log('divisors of 36 :', divisors(36));
console.log('of 1 and of 13 :', divisors(1), divisors(13));
console.log('odd count up to 50:', oddCount);
console.log('1e6 has', ofMillion.length, 'divisors, found in', workForMillion, 'iterations');
console.log('sum for 36     :', divisors(36).reduce((a, b) => a + b, 0));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34function divisors(n) {
  const small = [];
  const large = [];
  for (let d = 1; d * d <= n; d++) {
    if (n % d !== 0) continue;
    small.push(d);
    if (d !== n / d) large.push(n / d);
  }
  return [...small, ...large.reverse()];
}

const properDivisors = (n) => divisors(n).filter((d) => d !== n);
const aliquot = (n) => properDivisors(n).reduce((a, b) => a + b, 0);

function classify(n) {
  const sum = aliquot(n);
  if (sum === n) return 'perfect';
  return sum > n ? 'abundant' : 'deficient';
}

const perfect = [];
for (let n = 1; n < 10000; n++) if (classify(n) === 'perfect') perfect.push(n);

const abundantBelow100 = [];
for (let n = 1; n < 100; n++) if (classify(n) === 'abundant') abundantBelow100.push(n);

let firstOddAbundant = 0;
for (let n = 1; !firstOddAbundant; n += 2) if (classify(n) === 'abundant') firstOddAbundant = n;

console.log('proper divisors of 28 :', properDivisors(28), 'summing to', aliquot(28));
console.log('perfect below 10000   :', perfect);
console.log('abundant below 100    :', abundantBelow100.length, 'of them, starting', abundantBelow100.slice(0, 4));
console.log('smallest odd abundant :', firstOddAbundant);
console.log('220 and 284           :', aliquot(220), aliquot(284), '<- each other');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41function gcd(a, b) {
  a = Math.abs(a);
  b = Math.abs(b);
  while (b) [a, b] = [b, a % b];
  return a;
}

const gcdSteps = (a, b) => {
  let n = 0;
  a = Math.abs(a);
  b = Math.abs(b);
  while (b) {
    [a, b] = [b, a % b];
    n++;
  }
  return n;
};

const subtractionSteps = (a, b) => {
  let n = 0;
  while (a !== b) {
    if (a > b) a -= b;
    else b -= a;
    n++;
  }
  return n;
};

const fib = [1, 1];
while (fib.length < 14) fib.push(fib.at(-1) + fib.at(-2));
const fibStepCounts = fib.slice(0, 12).map((f, i) => gcdSteps(f, fib[i + 1]));

// The worst pair for subtraction: one small argument, one large.
const bySubtraction = subtractionSteps(1, 100000);
const byRemainder = gcdSteps(1, 100000);

console.log('gcd(48, 18)      :', gcd(48, 18));
console.log('gcd(1071, 462)   :', gcd(1071, 462), 'in', gcdSteps(1071, 462), 'remainder steps');
console.log('the same by subtraction:', subtractionSteps(1071, 462), 'steps');
console.log('gcd(1, 100000)   :', byRemainder, 'remainder steps against', bySubtraction, 'subtractions');
console.log('consecutive Fibonacci pairs cost:', fibStepCounts);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20const gcd = (a, b) => {
  a = Math.abs(a);
  b = Math.abs(b);
  while (b) [a, b] = [b, a % b];
  return a;
};

const lcmNaive = (a, b) => (a * b) / gcd(a, b);        // multiplies first
const lcm = (a, b) => (a / gcd(a, b)) * b;            // divides first

// Both share the factor 12345679, so the true LCM is small; only a * b is huge.
const a = 37037037;
const b = 283950617;

console.log('lcm(4, 6)       :', lcm(4, 6));
console.log('gcd * lcm       :', gcd(12, 18) * lcm(12, 18), 'and a * b:', 12 * 18);
console.log('gcd(a, b)       :', gcd(a, b));
console.log('a * b           :', a * b, '<- past 2**53, so already approximate');
console.log('multiply first  :', lcmNaive(a, b));
console.log('divide first    :', lcm(a, b));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19const gcd = (a, b) => {
  a = Math.abs(a);
  b = Math.abs(b);
  while (b) [a, b] = [b, a % b];
  return a;
};
const lcm = (a, b) => (a === 0 || b === 0 ? 0 : (a / gcd(a, b)) * b);

const gcdAll = (ns) => ns.reduce(gcd, 0);        // 0 is the identity for gcd
const lcmAll = (ns) => ns.reduce(lcm, 1);        // 1 is the identity for lcm

const upTo = (n) => Array.from({ length: n }, (_, i) => i + 1);

console.log('gcd of 12, 18, 24 :', gcdAll([12, 18, 24]));
console.log('lcm of 2, 3, 4, 5 :', lcmAll([2, 3, 4, 5]));
console.log('empty list        :', gcdAll([]), lcmAll([]));
console.log('lcm of 1..10      :', lcmAll(upTo(10)));
console.log('lcm of 1..20      :', lcmAll(upTo(20)));
console.log('lcm of 1..40      :', lcmAll(upTo(40)), 'safe?', Number.isSafeInteger(lcmAll(upTo(40))));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24const gcd = (a, b) => {
  a = Math.abs(a);
  b = Math.abs(b);
  while (b) [a, b] = [b, a % b];
  return a;
};

function simplify(numerator, denominator) {
  if (denominator === 0) return null;                    // not a fraction
  const g = gcd(numerator, denominator) || 1;            // gcd(0, 0) would be 0
  const sign = denominator < 0 ? -1 : 1;
  return [(sign * numerator) / g, (sign * denominator) / g];
}

// a/b + c/d = (ad + cb) / bd, then reduce.
const addFractions = (a, b, c, d) => simplify(a * d + c * b, b * d);

console.log('6/8      ->', simplify(6, 8));
console.log('3/-9     ->', simplify(3, -9));
console.log('-4/-8    ->', simplify(-4, -8));
console.log('0/5      ->', simplify(0, 5));
console.log('5/0      ->', simplify(5, 0));
console.log('1/10 + 2/10 as a fraction:', addFractions(1, 10, 2, 10));
console.log('the same sum in doubles  :', 0.1 + 0.2);