How to resolve the algorithm First perfect square in base n with n unique digits step by step in the JavaScript programming language
How to resolve the algorithm First perfect square in base n with n unique digits step by step in the JavaScript programming language
Table of Contents
Problem Statement
Find the first perfect square in a given base N that has at least N digits and exactly N significant unique digits when expressed in base N. E.G. In base 10, the first perfect square with at least 10 unique digits is 1026753849 (32043²). You may use analytical methods to reduce the search space, but the code must do a search. Do not use magic numbers or just feed the code the answer to verify it is correct.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm First perfect square in base n with n unique digits step by step in the JavaScript programming language
Summary:
The code solves a mathematical problem: finding the smallest perfect squares that use all digits from 0 to the given base (up to base 12). It uses a recursive algorithm to check whether the square of a given number uses all digits at the specified base.
Detailed Explanation:
Functions:
- allDigitSquare: The main function that takes a base as input and returns the smallest perfect square that uses all digits in that base.
- allDigitsUsedAtBase: A helper function that checks if the square of a given number uses all digits at the given base.
- showBaseSquare: A helper function that formats and displays the results in a table.
Constants:
- ceil, floor, sqrt: Standard Math functions for ceil, floor, and square root.
- Tuple: A constructor function for creating tuples (ordered pairs).
- digit: A function that maps an integer to its character representation as a digit.
- enumFromTo: A function that creates an array of integers from a start value to an end value.
- justifyRight: A function that aligns a string to the right with a specified filler character.
- print: A function for printing output to the console.
- quotRem: A function that splits an integer into its quotient and remainder when divided by another integer.
- replicate: A function that creates an array with a specified number of elements, all of the same value.
- showIntAtBase: A function that converts an integer to its string representation in the specified base.
- sj: A helper function for quick JSON stringification for testing purposes.
- str: A function that converts a value to a string.
- untilSucc: A function that returns the first integer in a sequence for which a given predicate returns true.
Main Function (main):
The main function calls allDigitSquare for each base from 2 to 12 and prints the results in a table.
allDigitSquare Function:
- Initializes an array of booleans, bools, to false for each digit in the given base.
- Uses untilSucc to find the smallest integer q for which allDigitsUsedAtBase(base, bools) returns true.
- Returns q.
allDigitsUsedAtBase Function:
- Takes a base, an array of booleans bools, and a number n as input.
- Computes the square of n and iterates over its digits in the given base.
- For each digit, sets the corresponding element in bools to true.
- Returns true if all elements in bools are true, indicating that all digits were used.
showBaseSquare Function:
- Formats and displays the results in a table, showing the base, the root, and the square for each base.
Source code in the javascript programming language
(() => {
'use strict';
// allDigitSquare :: Int -> Int
const allDigitSquare = base => {
const bools = replicate(base, false);
return untilSucc(
allDigitsUsedAtBase(base, bools),
ceil(sqrt(parseInt(
'10' + '0123456789abcdef'.slice(2, base),
base
)))
);
};
// allDigitsUsedAtBase :: Int -> [Bool] -> Int -> Bool
const allDigitsUsedAtBase = (base, bools) => n => {
// Fusion of representing the square of integer N at a given base
// with checking whether all digits of that base contribute to N^2.
// Sets the bool at a digit position to True when used.
// True if all digit positions have been used.
const ds = bools.slice(0);
let x = n * n;
while (x) {
ds[x % base] = true;
x = floor(x / base);
}
return ds.every(x => x)
};
// showBaseSquare :: Int -> String
const showBaseSquare = b => {
const q = allDigitSquare(b);
return justifyRight(2, ' ', str(b)) + ' -> ' +
justifyRight(8, ' ', showIntAtBase(b, digit, q, '')) +
' -> ' + showIntAtBase(b, digit, q * q, '');
};
// TEST -----------------------------------------------
const main = () => {
// 1-12 only - by 15 the squares are truncated by
// JS integer limits.
// Returning values through console.log –
// in separate events to avoid asynchronous disorder.
print('Smallest perfect squares using all digits in bases 2-12:\n')
(id > 0 ? chars.substr(id, 1) : " ") print('Base Root Square')
print(showBaseSquare(2));
print(showBaseSquare(3));
print(showBaseSquare(4));
print(showBaseSquare(5));
print(showBaseSquare(6));
print(showBaseSquare(7));
print(showBaseSquare(8));
print(showBaseSquare(9));
print(showBaseSquare(10));
print(showBaseSquare(11));
print(showBaseSquare(12));
};
// GENERIC FUNCTIONS ----------------------------------
const
ceil = Math.ceil,
floor = Math.floor,
sqrt = Math.sqrt;
// Tuple (,) :: a -> b -> (a, b)
const Tuple = (a, b) => ({
type: 'Tuple',
'0': a,
'1': b,
length: 2
});
// digit :: Int -> Char
const digit = n =>
// Digit character for given integer.
'0123456789abcdef' [n];
// enumFromTo :: (Int, Int) -> [Int]
const enumFromTo = (m, n) =>
Array.from({
length: 1 + n - m
}, (_, i) => m + i);
// justifyRight :: Int -> Char -> String -> String
const justifyRight = (n, cFiller, s) =>
n > s.length ? (
s.padStart(n, cFiller)
) : s;
// print :: a -> IO ()
const print = x => console.log(x)
// quotRem :: Int -> Int -> (Int, Int)
const quotRem = (m, n) =>
Tuple(Math.floor(m / n), m % n);
// replicate :: Int -> a -> [a]
const replicate = (n, x) =>
Array.from({
length: n
}, () => x);
// showIntAtBase :: Int -> (Int -> Char) -> Int -> String -> String
const showIntAtBase = (base, toChr, n, rs) => {
const go = ([n, d], r) => {
const r_ = toChr(d) + r;
return 0 !== n ? (
go(Array.from(quotRem(n, base)), r_)
) : r_;
};
return 1 >= base ? (
'error: showIntAtBase applied to unsupported base'
) : 0 > n ? (
'error: showIntAtBase applied to negative number'
) : go(Array.from(quotRem(n, base)), rs);
};
// Abbreviation for quick testing - any 2nd arg interpreted as indent size
// sj :: a -> String
function sj() {
const args = Array.from(arguments);
return JSON.stringify.apply(
null,
1 < args.length && !isNaN(args[0]) ? [
args[1], null, args[0]
] : [args[0], null, 2]
);
}
// str :: a -> String
const str = x => x.toString();
// untilSucc :: (Int -> Bool) -> Int -> Int
const untilSucc = (p, x) => {
// The first in a chain of successive integers
// for which p(x) returns true.
let v = x;
while (!p(v)) v = 1 + v;
return v;
};
// MAIN ---
return main();
})();
You may also check:How to resolve the algorithm Haversine formula step by step in the Ruby programming language
You may also check:How to resolve the algorithm Calendar step by step in the Yabasic programming language
You may also check:How to resolve the algorithm 24 game step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Jump anywhere step by step in the D programming language
You may also check:How to resolve the algorithm Zeckendorf number representation step by step in the Tcl programming language