How to resolve the algorithm Wasteful, equidigital and frugal numbers step by step in the Julia programming language

Published on 22 June 2024 08:30 PM
#Julia

How to resolve the algorithm Wasteful, equidigital and frugal numbers step by step in the Julia programming language

Table of Contents

Problem Statement

Let n be a positive integer and l(n) be the number of its digits in base b. Express n as the product of its prime factors raised to the appropriate powers. Let D(n) be the total number of its base b digits in all its prime factors and in all their exponents that are greater than 1. Then n is defined to be:

  1. a wasteful (or extravagant) number if l(n) < D(n); or
  2. an equidigital number if l(n) = D(n); or
  3. a frugal (or economical) number if l(n) > D(n) in base b. By convention, the number 1 is considered to be an equidigital number in any base even though it has no prime factors. For the avoidance of any doubt, the number 0 is not a positive integer (and arguably not a natural number either) and so is excluded from all 3 categories. An economical number is sometimes defined as being one for which l(n) >= D(n) though this usage won't be followed here.

In base 10, the number 30 has a prime factorization of 2 x 3 x 5. The total number of digits is 3 (all exponents being 1) which is more than the 2 digits 30 has. So 30 is wasteful in base 10. In base 10, the number 49 has a prime factorization of 7². The total number of digits, including those of the exponent, is 2 which is the same as the 2 digits 49 has. So 49 is equidigital in base 10. In base 10, the number 125 has a prime factorization of 5³. The total number of digits, including those of the exponent, is 2 which is less than the 3 digits 125 has. So 125 is frugal in base 10. In base 2, the number 100000 (32 decimal) has a prime factorization of 10^101 (2^5 decimal). The total number of binary digits, including those of the exponent, is 5 which is less than the 6 binary digits 100000 has. So 32 is frugal in base 2 (but equidigital in base 10).

Compute and show here the first 50 and the 10,000th number in base 10 for each of the three categories of number defined above. Also compute and show how many numbers less than 1,000,000 fall into each of the three categories.

Do the same for base 11, but show the results in base 10.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Wasteful, equidigital and frugal numbers step by step in the Julia programming language

This Julia code explores the relationship between the factor expansion of numbers and their digit counts in different bases. A brief explanation of the functionality:

  1. The wastefulness function calculates the wastefulness of a given integer n in a specific base. Wastefulness is determined by comparing the number of digits required to represent the factor expansion of n versus the number of digits required to represent n itself.
  2. The function factor(n) from the Primes package is used to factorize n into its prime factors.
  3. The ndigits function is used to count the number of digits of a number in a given base.
  4. The wastefulness function returns -1 if the number is frugal (factor expansion requires more digits), 0 if it's equidigital (same number of digits in both representations), and 1 if it's wasteful (factor expansion requires fewer digits).
  5. The code iterates through a range of integers from 1 to 10,000,000 and calculates the wastefulness for each integer in bases 10 and 11.
  6. As it iterates, it collects lists of the first 50 wasteful, equidigital, and frugal numbers in each base.
  7. It also counts the total occurrences of wasteful, equidigital, and frugal numbers among the first million integers.
  8. Once the 10,000th wasteful number is found for a base, it prints out the following information:
    • The first 50 wasteful, equidigital, and frugal numbers in that base.
    • The 10,000th wasteful, equidigital, and frugal numbers.
    • The counts of wasteful, equidigital, and frugal numbers among the first million integers.

The code then repeats the process for base 11.

The output of the code demonstrates the distribution of wasteful, equidigital, and frugal numbers in different bases. It also shows how the wastefulness of numbers varies as the range of integers increases.

Source code in the julia programming language

using Primes

"""
    function wastefulness(n, base = 10)
    
calculate d1: the number of digits in base `base` required to write the factor expansion of
`n`, ie 12 -> 2^2 * 3^2 is 4 digits, 7 -> 7 is 1 digit, 20 -> 5 * 2^2 is 3 digits

calculate d2: the number of digits in base `base` to represent `n` itself

return -1 if frugal (d1 > d2), 0 if equidigital (d1 == d2), 1 if wasteful (d1 > d2)
"""
function wastefulness(n::Integer, base = 10)
    @assert n > 0
    return n == 1 ? 0 : 
       sign(sum(p -> ndigits(p[1], base=base) + 
       (p[2] == 1 ? 0 : ndigits(p[2], base=base)),
       factor(n).pe) - 
       ndigits(n, base=base))
end

for b in [10, 11]
    w50, e50, f50 = Int[], Int[], Int[]
    w10k, e10k, f10k, wcount, ecount, fcount, wm, em, fm = 0, 0, 0, 0, 0, 0, 0, 0, 0
    for n in 1:10_000_000
        sgn = wastefulness(n, b)
        if sgn < 0
            fcount < 50 && push!(f50, n)
            fcount += 1
            fcount == 10000 &&(f10k = n)
            n < 1_000_000 && (fm += 1)
        elseif sgn == 0
            ecount < 50 && push!(e50, n)
            ecount += 1
            ecount == 10000 && (e10k = n)
            n < 1_000_000 && (em += 1)
        else # sgn > 0
            wcount < 50 && push!(w50, n)
            wcount += 1
            wcount == 10000  && (w10k = n)
            n < 1_000_000 && (wm += 1)
        end
        if f10k > 0
            println("FOR BASE $b:\n")
            println("First 50 Wasteful numbers:")
            foreach(p -> print(rpad(p[2], 5), p[1] % 10 == 0 ? "\n" : ""), pairs(w50))
            println("\nFirst 50 Equidigital numbers:")
            foreach(p -> print(rpad(p[2], 5), p[1] % 10 == 0 ? "\n" : ""), pairs(e50))
            println("\nFirst 50 Frugal numbers:")
            foreach(p -> print(rpad(p[2], 5), p[1] % 10 == 0 ? "\n" : ""), pairs(f50))
            println("\n10,000th Wasteful number   : $w10k")
            println("10,000th Equidigital number  : $e10k")
            println("10,000th Frugal number       : $f10k")
            println("\nFor natural numbers < 1 million, the breakdown is as follows:")
            println("  Wasteful numbers    : $wm")
            println("  Equidigital numbers : $em")
            println("  Frugal numbers      : $fm\n\n")
            break
        end
    end
end

You may also check:How to resolve the algorithm Program name step by step in the R programming language
You may also check:How to resolve the algorithm Roman numerals/Encode step by step in the Eiffel programming language
You may also check:How to resolve the algorithm Echo server step by step in the Oz programming language
You may also check:How to resolve the algorithm Happy numbers step by step in the C# programming language
You may also check:How to resolve the algorithm Range extraction step by step in the Delphi programming language