How to resolve the algorithm First perfect square in base n with n unique digits step by step in the JavaScript programming language

Published on 12 May 2024 09:40 PM

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