Colorful numbers: Difference between revisions

Content added Content deleted

Inline

Revision as of 00:56, 7 April 2022

A colorful number is a non-negative base 10 integer where the product of every sub group of consecutive digits is unique.

E.G.

24753 is a colorful number. 2, 4, 7, 5, 3, (2×4)8, (4×7)28, (7×5)35, (5×3)15, (2×4×7)56, (4×7×5)140, (7×5×3)105, (2×4×7×5)280, (4×7×5×3)420, (2×4×7×5×3)840

Every product is unique.

2346 is not a colorful number. 2, 3, 4, 6, (2×3)6, (3×4)12, (4×6)24, (2×3×4)48, (3×4×6)72, (2×3×4×6)144

The product 6 is repeated.

Single digit numbers are considered to be colorful. A colorful number larger than 9 cannot contain a repeated digit, the digit 0 or the digit 1. As a consequence, there is a firm upper limit for colorful numbers; no colorful number can have more than 8 digits.

Task

Write a routine (subroutine, function, procedure, whatever it may be called in your language) to test if a number is a colorful number or not.
Use that routine to find all of the colorful numbers less than 100.
Use that routine to find the largest possible colorful number.

Stretch

Find and display the count of colorful numbers in each order of magnitude.
Find and show the total count of all colorful numbers.

Colorful numbers have no real number theory application. They are more a recreational math puzzle than a useful tool.

Factor

Works with: Factor version 0.99 2021-06-02

<lang factor>USING: assocs grouping grouping.extras io kernel literals math math.combinatorics math.ranges prettyprint project-euler.common sequences sequences.extras sets ;

CONSTANT: digits $[ 2 9 [a..b] ]

(colorful?) ( seq -- ? )

   all-subseqs [ product ] map all-unique? ;

colorful? ( n -- ? )

   [ t ] [ number>digits (colorful?) ] if-zero ;

table. ( seq cols -- )

   [ "" pad-groups ] keep group simple-table. ;

(oom-count) ( n -- count )

   digits swap <k-permutations> [ (colorful?) ] count ;

oom-count ( n -- count )

   dup 1 = [ drop 10 ] [ (oom-count) ] if ;

"Colorful numbers under 100:" print 100 <iota> [ colorful? ] filter 10 table. nl

"Largest colorful number:" print digits <permutations> [ (colorful?) ] find-last nip digits>number . nl

"Count of colorful numbers by number of digits:" print 8 [1..b] [ oom-count ] zip-with dup . "Total: " write values sum .</lang>

Output:

Colorful numbers under 100:
0  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          

Largest colorful number:
98746253

Count of colorful numbers by number of digits:
{
    { 1 10 }
    { 2 56 }
    { 3 328 }
    { 4 1540 }
    { 5 5514 }
    { 6 13956 }
    { 7 21596 }
    { 8 14256 }
}
Total: 57256

Haskell

This example is incorrect. Please fix the code and remove this message.

Details: 98765432 is not a Colorful number; 6×5×4 == 5×4×3×2 == 120

<lang haskell>import Data.List ( nub ) import Data.List.Split ( divvy ) import Data.Char ( digitToInt )

isColourful :: Integer -> Bool isColourful n

  |n >= 0 && n <= 10 = True
  |n > 10 && n < 100 = ((length s) == (length $ nub s)) &&
   (not $ any (\c -> elem c "01") s)
  |n >= 100 = ((length s) == (length $ nub s)) && (not $ any (\c -> elem c "01") s)
    && ((length products) == (length $ nub products))
   where
    s :: String
    s = show n
    products :: [Int]
    products = map (\p -> (digitToInt $ head p) * (digitToInt $ last p))
     $ divvy 2 1 s

solution1 :: [Integer] solution1 = filter isColourful [0 .. 100]

solution2 :: Integer solution2 = head $ filter isColourful [98765432, 98765431 ..]</lang>

Output:

[0,1,2,3,4,5,6,7,8,9,10,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](solution1)
98765432(solution2)

J

<lang J> colorful=: {{(-:~.);<@(*/\)\. 10 #.inv y}}"0

  I.colorful i.100

0 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

  C=: I.colorful <.i.1e8
  >./C

98746253

  (~.,. #/.~) 10 <.@^. C

__ 1

57256</lang>

(Note that 0, here is a different order of magnitude than 1.)

Julia

This example is incomplete. Missing third part of task - Find largest possible colorful number.
Please ensure that it meets all task requirements and remove this message.

<lang julia>function iscolorful(n, base=10)

   0 <= n < 10 && return true
   dig = digits(n, base=base)
   (1 in dig || 0 in dig || !allunique(dig)) && return false
   products = Set(dig)
   for i in 2:length(dig), j in 1:length(dig)-i+1
       p = prod(dig[j:j+i-1])
       p in products && return false
       push!(products, p)
   end
   return true

end

function testcolorfuls()

   println("Colorful numbers for 1:25, 26:50, 51:75, and 76:100:")
   for i in 1:100
       iscolorful(i) && print(rpad(i, 5))
       i % 25 == 0 && println()
   end
   csum = 0
   for i in 0:7
       j, k = i == 0 ? 0 : 10^i, 10^(i+1) - 1
       n = count(i -> iscolorful(i), j:k)
       csum += n
       println("The count of colorful numbers between $j and $k is $n.")
   end
   println("The total number of colorful numbers is $csum.")

end

testcolorfuls()

</lang>

Output:

Colorful numbers for 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 count of colorful numbers between 0 and 9 is 10.
The count of colorful numbers between 10 and 99 is 56.
The count of colorful numbers between 100 and 999 is 328.
The count of colorful numbers between 1000 and 9999 is 1540.
The count of colorful numbers between 10000 and 99999 is 5514.
The count of colorful numbers between 100000 and 999999 is 13956.
The count of colorful numbers between 1000000 and 9999999 is 21596.
The count of colorful numbers between 10000000 and 99999999 is 14256.
The total number of colorful numbers is 57256.

Perl

Translation of: Raku

<lang perl>use strict; use warnings; use feature 'say'; use enum qw(False True); use List::Util <max uniqint product>; use Algorithm::Combinatorics qw(combinations permutations);

sub table { my $t = shift() * (my $c = 1 + length max @_); ( sprintf( ('%'.$c.'d')x@_, @_) ) =~ s/.{1,$t}\K/\n/gr }

sub is_colorful {

   my($n) = @_;
   return True if 0 <= $n and $n <= 9;
   return False if $n =~ /0|1/ or $n < 0;
   my @digits = split , $n;
   return False unless @digits == uniqint @digits;
   my @p;
   for my $w (0 .. @digits) {
       push @p, map { product @digits[$_ .. $_+$w] } 0 .. @digits-$w-1;
       return False unless @p == uniqint @p
   }
   True

}

say "Colorful numbers less than 100:\n" . table 10, grep { is_colorful $_ } 0..100;

my $largest = 98765432; 1 while not is_colorful --$largest; say "Largest magnitude colorful number: $largest\n";

my $total= 10; map { is_colorful(join , @$_) and $total++ } map { permutations $_ } combinations [2..9], $_ for 2..8; say "Total colorful numbers: $total";</lang>

Output:

Colorful numbers less than 100:
  0  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

Largest magnitude colorful number: 98746253

Total colorful numbers: 57256

Phix

Library: Phix/online

You can run this online here.

with javascript_semantics
function colourful(integer n)
    if n<10 then return n>=0 end if
    sequence digits = sq_sub(sprintf("%d",n),'0'),
                 ud = unique(deep_copy(digits))
    integer ln = length(digits)
    if ud[1]<=1 or length(ud)!=ln then return false end if
    for i=1 to ln-1 do
        for j=i+1 to ln do
           atom prod = product(digits[i..j])
           if find(prod,ud) then return false end if
           ud &= prod
        end for
    end for
    return true
end function
 
atom t0 = time()
sequence cn = apply(true,sprintf,{{"%2d"},filter(tagset(100,0),colourful)})
printf(1,"The %d colourful numbers less than 100 are:\n%s\n",
         {length(cn),join_by(cn,1,10,"  ")})

sequence count = repeat(0,8),
         used = repeat(false,10)
integer largestcn = 0

procedure count_colourful(integer taken=0, string n="")
    if taken=0 then
        for digit='0' to '9' do
            integer dx = digit-'0'+1
            used[dx] = true
            count_colourful(iff(digit<'2'?9:1),""&digit)
            used[dx] = false
        end for
    else
        integer nn = to_integer(n)
        if colourful(nn) then
            integer ln = length(n)
            count[ln] += 1
            if nn>largestcn then largestcn = nn end if
        end if
        if taken<9 then
            for digit='2' to '9' do
                integer dx = digit-'0'+1
                if not used[dx] then
                    used[dx] = true
                    count_colourful(taken+1,n&digit)
                    used[dx] = false
                end if
            end for
        end if
    end if
end procedure
count_colourful()
printf(1,"The largest possible colourful number is: %,d\n\n",largestcn)
atom pow = 10
for dc=1 to length(count) do
    printf(1,"  %d digit colourful number count: %,6d - %7.3f%%\n",
               {dc, count[dc], 100*count[dc]/pow})
    pow = iff(pow=10?90:pow*10)
end for
printf(1,"\nTotal colourful numbers: %,d\n", sum(count))
?elapsed(time()-t0)

Output:

The 66 colourful numbers less than 100 are:
 0   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 largest possible colourful number is: 98,746,253

  1 digit colourful number count:     10 - 100.000%
  2 digit colourful number count:     56 -  62.222%
  3 digit colourful number count:    328 -  36.444%
  4 digit colourful number count:  1,540 -  17.111%
  5 digit colourful number count:  5,514 -   6.127%
  6 digit colourful number count: 13,956 -   1.551%
  7 digit colourful number count: 21,596 -   0.240%
  8 digit colourful number count: 14,256 -   0.016%

Total colourful numbers: 57,256
"1.9s"

Raku

<lang perl6>sub is-colorful (Int $n) {

   return True if 0 <= $n <= 9;
   return False if $n.contains(0) || $n.contains(1) || $n < 0;
   my @digits = $n.comb;
   my %sums = @digits.Bag;
   return False if %sums.values.max > 1;
   for 2..@digits -> $group {
       @digits.rotor($group => 1 - $group).map: { %sums{ [×] $_ }++ }
       return False if %sums.values.max > 1;
   }
   True

}

put "Colorful numbers less than 100:\n" ~ (^100).race.grep( &is-colorful).batch(10)».fmt("%2d").join: "\n";

my ($start, $total) = 23456789, 10;

print "\nLargest magnitude colorful number: "; .put and last if .Int.&is-colorful for $start.flip … $start;

put "\nCount of colorful numbers for each order of magnitude:\n" ~

   "1 digit colorful number count: $total - 100%";

for 2..8 {

  put "$_ digit colorful number count: ",
  my $c = +(flat $start.comb.combinations($_).map: {.permutations».join».Int}).race.grep( &is-colorful ),
  " - {($c / (exp($_,10) - exp($_-1,10) ) * 100).round(.001)}%";
  $total += $c;

}

say "\nTotal colorful numbers: $total";</lang>

Output:

Colorful numbers less than 100:
 0  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

Largest magnitude colorful number: 98746253

Count of colorful numbers for each order of magnitude:
1 digit colorful number count: 10 - 100%
2 digit colorful number count: 56 - 62.222%
3 digit colorful number count: 328 - 36.444%
4 digit colorful number count: 1540 - 17.111%
5 digit colorful number count: 5514 - 6.127%
6 digit colorful number count: 13956 - 1.551%
7 digit colorful number count: 21596 - 0.24%
8 digit colorful number count: 14256 - 0.016%

Total colorful numbers: 57256

Wren

Translation of: Phix

Library: Wren-math

Library: Wren-set

Library: Wren-seq

Library: Wren-fmt

<lang ecmascript>import "./math" for Int, Nums import "./set" for Set import "./seq" for Lst import "./fmt" for Fmt

var isColorful = Fn.new { |n|

   if (n < 0) return false
   if (n < 10) return true
   var digits = Int.digits(n)
   if (digits.contains(0) || digits.contains(1)) return false
   var set = Set.new(digits)
   var dc = digits.count
   if (set.count < dc) return false
   for (k in 2..dc) {
       for (i in 0..dc-k) {
          var prod = 1
          for (j in i..i+k-1) prod = prod * digits[j]
          if (set.contains(prod)) return false
          set.add(prod)
       }
   }
   return true

}

var count = List.filled(9, 0) var used = List.filled(11, false) var largest = 0

var countColorful // recursive countColorful = Fn.new { |taken, n|

   if (taken == 0) {
       for (digit in 0..9) {
           var dx = digit + 1
           used[dx] = true
           countColorful.call((digit < 2) ? 9 : 1, String.fromByte(digit + 48))
           used[dx] = false
       }
   } else {
       var nn = Num.fromString(n)
       if (isColorful.call(nn)) {
           var ln = n.count
           count[ln] = count[ln] + 1
           if (nn > largest) largest = nn
       }
       if (taken < 9) {
           for (digit in 2..9) {
               var dx = digit + 1
               if (!used[dx]) {
                   used[dx] = true
                   countColorful.call(taken + 1, n + String.fromByte(digit + 48))
                   used[dx] = false
               }
           }
       }
   }

}

var cn = (0..99).where { |i| isColorful.call(i) }.toList System.print("The %(cn.count) colorful numbers less than 100 are:") for (chunk in Lst.chunks(cn, 10)) Fmt.print("$2d", chunk)

countColorful.call(0, "") System.print("\nThe largest possible colorful number is:") Fmt.print("$,d\n", largest)

System.print("Count of colorful numbers for each order of magnitude:") var pow = 10 for (dc in 1...count.count) {

   Fmt.print("  $d digit colorful number count: $,6d - $7.3f\%", dc, count[dc], 10 * count[dc] / pow)
   pow = (pow == 10) ? 90 : pow * 10

}

Fmt.print("\nTotal colorful numbers: $,d", Nums.sum(count))</lang>

Output:

The 66 colorful numbers less than 100 are:
 0  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 largest possible colorful number is:
98,746,253

Count of colorful numbers for each order of magnitude:
  1 digit colorful number count:     10 - 100.000%
  2 digit colorful number count:     56 -  62.222%
  3 digit colorful number count:    328 -  36.444%
  4 digit colorful number count:  1,540 -  17.111%
  5 digit colorful number count:  5,514 -   6.127%
  6 digit colorful number count: 13,956 -   1.551%
  7 digit colorful number count: 21,596 -   0.240%
  8 digit colorful number count: 14,256 -   0.016%

Total colorful numbers: 57,256

XPL0

<lang XPL0>func IPow(A, B); \A^B int A, B, T, I; [T:= 1; for I:= 1 to B do T:= T*A; return T; ];

func Colorful(N); \Return 'true' if N is a colorful number int N, Digits, R, I, J, Prod; def Size = 9*8*7*6*5*4*3*2 + 1; char Used(Size), Num(10); [if N < 10 then return true; \single digit number is colorful FillMem(Used, false, 10); \digits must be unique Digits:= 0; repeat N:= N/10; \slice digits off N

       R:= rem(0);
       if N=1 or R=0 or R=1 then return false;
       if Used(R) then return false;
       Used(R):= true;         \digits must be unique
       Num(Digits):= R;
       Digits:= Digits+1;

until N = 0; FillMem(Used+10, false, Size-10); \products must be unique for I:= 0 to Digits-2 do

   [Prod:= Num(I);
   for J:= I+1 to Digits-1 do
       [Prod:= Prod * Num(J);
       if Used(Prod) then return false;
       Used(Prod):= true;
       ];
   ];

return true; ];

int Count, N, Power, Total; [Text(0, "Colorful numbers less than 100: "); Count:= 0; for N:= 0 to 99 do

   if Colorful(N) then
       [IntOut(0, N);
       Count:= Count+1;
       if rem(Count/10) then ChOut(0, 9\tab\) else CrLf(0);
       ];

Text(0, "

Largest magnitude colorful number: "); N:= 98_765_432; loop [if Colorful(N) then quit;

       N:= N-1;
       ];

IntOut(0, N); Text(0, "

Count of colorful numbers for each order of magnitude: "); Total:= 0; for Power:= 1 to 8 do

   [Count:= if Power=1 then 1 else 0;
   for N:= IPow(10, Power-1) to IPow(10, Power)-1 do
       if Colorful(N) then Count:= Count+1;
   IntOut(0, Power);
   Text(0, " digit colorful number count: ");
   IntOut(0, Count);
   CrLf(0);
   Total:= Total + Count;
   ];

Text(0, " Total colorful numbers: "); IntOut(0, Total); CrLf(0); ]</lang>

Output:

Colorful numbers less than 100:
0       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      

Largest magnitude colorful number: 98746253

Count of colorful numbers for each order of magnitude:
1 digit colorful number count: 10
2 digit colorful number count: 56
3 digit colorful number count: 328
4 digit colorful number count: 1540
5 digit colorful number count: 5514
6 digit colorful number count: 13956
7 digit colorful number count: 21596
8 digit colorful number count: 14256

Total colorful numbers: 57256