Engee documentation
Notebook

The algorithm for calculating "Colored numbers"

This example demonstrates the implementation of the algorithm for searching for "colored numbers" in the Julia programming language.

Introduction

What are colored numbers?

A colored number is a natural number in which all the digits are different, and all possible products of consecutive digits are also different. For example, the number it is colored because:

  • numbers and different;
  • the product of all the digits () differs from the numbers themselves;
  • there are no more works.
    If we take the number Then we should check the following works:
  • one digit at a time: , , ;
  • two digits each: , ;
  • three digits each: .
    All these values are unique → the number is "colored".

Function iscolorful

Checks whether a given number is "colored"

Arguments:

  • n: an integer to check
  • base: number system (default is 10)

Returns: true/false

In [ ]:
function iscolorful(n, base=10)
    # If the number is less than 10, it is automatically considered colored.
    0 <= n < 10 && return true
    
    # We get an array of digits of the number
    dig = digits(n, base=base)

    # We exclude the cases: the presence of 1 or 0,
    # or duplicate numbers – such numbers are definitely not colored.
    (1 in dig || 0 in dig || !allunique(dig)) && return false

    # We create a set of unique values, starting with individual digits.
    products = Set(dig)

    # We go through all substrings of length >= 2
    # i is the length of the substring (from 2 to the length of the number)
    # j is the starting position of the substring.
    for i in 2:length(dig), j in 1:length(dig)-i+1
        # Calculating the product of the digits in the current group
        p = prod(dig[j:j+i-1])

        # If such a value has already been encountered, the number is not colored.
        p in products && return false
        
        # Adding a new piece to the set
        push!(products, p)
    end

    # Updating the global variable of the maximum color number found
    if n > largest
        global largest = n
    end

    return true
end
Out[0]:
iscolorful
In [ ]:
# A global variable for storing the largest colored number
largest = 0;

Testing functionality (testcolorfuls)

This function outputs a list of colored numbers from 1 to 100, and then counts the number of colored numbers in each decimal interval.

In [ ]:
function testcolorfuls()
    println("Colored numbers for ranges 1:25, 26:50, 51:75, and 76:100:")

    # Cycle through the numbers from 1 to 100
    for i in 1:100
        # If the number is colored, we output it with formatting.
        iscolorful(i) && print(rpad(i, 5))

        # Line break every 25 numbers
        i % 25 == 0 && println()
    end

    csum = 0 # A common color number counter

    # Counting the colored numbers in the ranges:
    # [0..9], [10..99], ..., [10^7...10^8)
    for i in 0:7
        # The beginning and ending elements of the interval
        j, k = i == 0 ? 0 : 10^i, 10^(i+1) - 1

        # We count the number of colored numbers in the interval
        n = count(ii -> iscolorful(ii), j:k)

        csum += n

        # Printing the result
        println("The number of colored numbers between $(lpad(j,9)) and $(lpad(k,9)) is $n.")
    end

    # Final message
    println("The maximum possible color number is $largest.")
    println("The total number of colored numbers is $csum.")
end
Out[0]:
testcolorfuls (generic function with 1 method)

Calling the test function

Let's run the main code to get the result.

In [ ]:
testcolorfuls()
Colored numbers for ranges 1:25, 26:50, 51:75, and 76:100:
1    2    3    4    5    6    7    8    9    23   24   25   
26   27   28   29   32   34   35   36   37   38   39   42   43   45   46   47   48   49   
52   53   54   56   57   58   59   62   63   64   65   67   68   69   72   73   74   75   
76   78   79   82   83   84   85   86   87   89   92   93   94   95   96   97   98   
The number of colored numbers between 0 and 9 is 10.
The number of colored numbers between 10 and 99 is 56.
The number of colored numbers between 100 and 999 is 328.
The number of colored numbers between 1000 and 9999 is 1540.
The number of colored numbers between 10000 and 99999 is 5514.
The number of colored numbers between 100,000 and 999999 is 13956.
The number of colored numbers between 1000000 and 9999999 is 21596.
The number of colored numbers between 10000000 and 99999999 is 14256.
The maximum possible color number is 98746253.
The total number of colored numbers is 57256.

Conclusion

We have reviewed the implementation of the concept of a "colored number" in the Julia language. The program allows you to find such numbers, determine their uniqueness within the specified boundaries, as well as calculate their total number and maximum among them.
This is useful in studying the properties of numbers and can be applied in number theory problems or logic puzzles.
It uses working with sets, recursive analysis of subarrays, and management of global variables.

The example was developed using materials from Rosetta Code