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 a number
    dig = digits(n, base=base)

    # We exclude cases: 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()
Цветные числа для диапазонов 1:25, 26:50, 51:75, и 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   
Количество цветных чисел между         0 и         9 - 10.
Количество цветных чисел между        10 и        99 - 56.
Количество цветных чисел между       100 и       999 - 328.
Количество цветных чисел между      1000 и      9999 - 1540.
Количество цветных чисел между     10000 и     99999 - 5514.
Количество цветных чисел между    100000 и    999999 - 13956.
Количество цветных чисел между   1000000 и   9999999 - 21596.
Количество цветных чисел между  10000000 и  99999999 - 14256.
Максимально возможное цветное число - 98746253.
Общее количество цветных чисел - 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, and 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