Sort the unique numbers in a multiplication table

Question

Pretty simple challenge today:

Write a program or function that takes in a positive integer N and prints or returns a sorted list of the unique numbers that appear in the multiplication table whose row and column multiplicands both range from 1 to N inclusive.

The list may be sorted in ascending order (smallest to largest) or descending order (largest to smallest), and may be output in any reasonable format.

The shortest code in bytes wins!

Example

When N = 4, the multiplication table looks like:

   1  2  3  4
  -----------
1| 1  2  3  4
 |
2| 2  4  6  8
 |
3| 3  6  9 12
 |
4| 4  8 12 16

The unique numbers in the table are 1, 2, 3, 4, 6, 8, 9, 12, 16. These are already sorted, so

1, 2, 3, 4, 6, 8, 9, 12, 16

might be your exact output for N = 4. But since the sorting can be reversed and there's some leeway in the formatting, these would also be valid outputs:

[16,12,9,8,6,4,3,2,1]

1
2
3
4
6
8
9
12
16

16 12 9 8 4 3 2 1

Test Cases

N=1 -> [1]
N=2 -> [1, 2, 4]
N=3 -> [1, 2, 3, 4, 6, 9]
N=4 -> [1, 2, 3, 4, 6, 8, 9, 12, 16]
N=5 -> [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 20, 25]
N=6 -> [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 30, 36]
N=7 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 28, 30, 35, 36, 42, 49]
N=8 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 28, 30, 32, 35, 36, 40, 42, 48, 49, 56, 64]
N=9 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36, 40, 42, 45, 48, 49, 54, 56, 63, 64, 72, 81]
N=10 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36, 40, 42, 45, 48, 49, 50, 54, 56, 60, 63, 64, 70, 72, 80, 81, 90, 100]
N=11 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32, 33, 35, 36, 40, 42, 44, 45, 48, 49, 50, 54, 55, 56, 60, 63, 64, 66, 70, 72, 77, 80, 81, 88, 90, 99, 100, 110, 121]
N=12 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32, 33, 35, 36, 40, 42, 44, 45, 48, 49, 50, 54, 55, 56, 60, 63, 64, 66, 70, 72, 77, 80, 81, 84, 88, 90, 96, 99, 100, 108, 110, 120, 121, 132, 144]

Answer 1

Pyth, 8 bytes

S{*M^SQ2

Try it online.

Explanation: SQ takes the evaluated list input (Q) and makes a list [1, 2, ..., Q]. ^SQ2 takes the Cartesian product of that list with itself - all possible product combinations. *M multiplies all these pairs together to form all possible results in the multiplication table and S{ makes it unique and sorts it.

Answer 2

Python 2, 61 51 bytes

lambda n:sorted({~(i%n)*~(i/n)for i in range(n*n)})

Thanks to xnor for shortening some syntax.

Answer 3

APL, 18 16 bytes

{y[⍋y←∪,∘.×⍨⍳⍵]}

This is an unnamed monadic function. The output is in ascending order.

Explanation:

             ⍳⍵]}   ⍝ Get the integers from 1 to the input
         ∘.×⍨       ⍝ Compute the outer product of this with itself
        ,           ⍝ Flatten into an array
       ∪            ⍝ Select unique elements
     y←             ⍝ Assign to y
 {y[⍋               ⍝ Sort ascending

Fixed an issue and saved 2 bytes thanks to Thomas Kwa!

Answer 4

CJam, 14 12 bytes

Latest version with improvements proposed by @aditsu:

{)2m*::*0^$}

This is an anonymous function. Try it online, with input/output code needed for testing it.

@Martin proposed another very elegant solution ({,:)_ff*:|$}) with the same length. I used the one by aditsu because it was much more similar to my original solution.

The main difference to my original solution is that this keeps the 0 value in the original sequence, which saves 2 bytes at the start. You'd think that this would not help, because you have to remove the 0 value from the result. But the core of @aditsu's idea is the 0^ at the end, which is a set difference with 0. This removes the 0, and at the same time, since it's a set operation, eliminates duplicate elements from the solution set. Since I already needed 2 bytes to eliminate the duplicates before, removing the 0 is then essentially free.

Explanation:

{     Start anonymous function.
  )     Increment to get N+1.
  2m*   Cartesian power, to get all pairs of numbers in range [0, N].
  ::*   Reduce all pairs with multiplication.
  0^    Remove 0, and remove duplicates at the same time since this is a set operation.
  $     Sort the list.
}     End anonymous function.

Answer 5

Octave, 22 bytes

@(n)unique((a=1:n)'*a)

Answer 6

Julia, 24 bytes

n->sort(∪((x=1:n)*x'))

This is an anonymous function that accepts an integer and returns an integer array.

Ungolfed:

function f(n::Integer)
    # Construct a UnitRange from 1 to the input
    x = 1:n

    # Compute the outer product of x with itself
    o = x * transpose(x)

    # Get the unique elements, implicitly flattening
    # columnwise into an array
    u = unique(o)

    # Return the sorted output
    return sort(u)
end

Answer 7

MATLAB, 24 bytes

@(n)unique((1:n)'*(1:n))

Answer 8

Ruby, 50 48 bytes

->n{c=*r=1..n;r.map{|i|c|=r.map{|j|i*j}};c.sort}

Ungolfed:

->n {
  c=*r=1..n
  r.map { |i| c|=r.map{|j|i*j} }
  c.sort
}

Using nested loop to multiply each number with every other number upto n and then sorting the array.

50 bytes

->n{r=1..n;r.flat_map{|i|r.map{|j|i*j}}.uniq.sort}

Usage:

->n{c=*r=1..n;r.map{|i|c|=r.map{|j|i*j}};c.sort}[4]
=> [1, 2, 3, 4, 6, 8, 9, 12, 16]

Answer 9

zsh, 86 56 bytes

thanks to @Dennis for saving 30(!) bytes

(for a in {1..$1};for b in {1..$1};echo $[a*b])|sort -nu

Explanation / ungolfed:

(                      # begin subshell
  for a in {1..$1}     # loop through every pair of multiplicands
    for b in {1..$1}
      echo $[a*b]      # calculate a * b, output to stdout
) | sort -nu           # pipe output of subshell to `sort -nu', sorting
                       # numerically (-n) and removing duplicates (-u for uniq)

This doesn't work in Bash because Bash doesn't expand {1..$1}—it just interprets it literally (so, a=5; echo {1..$a} outputs {1..5} instead of 1 2 3 4 5).

Answer 10

R, 39 bytes

cat(unique(sort(outer(n<-1:scan(),n))))

This reads an integer from STDIN and writes a space delimited list to STDOUT.

We create the multiplication table as a matrix using outer, implicitly flatten into a vector and sort using sort, select unique elements using unique, and print space delimited using cat.

Answer 11

Mathematica, 25 bytes

Union@@Array[1##&,{#,#}]&

Answer 12

K, 17 bytes

t@<t:?,/t*\:t:1+!

Not much to say here. Sort (t@<t:) the unique items (?) of the flattened (,/) multiplied cartesian self-product (t*\:t:) of 1 up to and including N (1+!).

In action:

  t@<t:?,/t*\:t:1+!5
1 2 3 4 5 6 8 9 10 12 15 16 20 25

Answer 13

Haskell, 55 54 bytes

import Data.List
f n=sort$nub[x*y|x<-[1..n],y<-[1..x]]

Usage example: f 4 -> [1,2,3,4,6,8,9,12,16].

nub removes duplicate elements from a list.

Edit: @Zgarb found a superfluous $.

Answer 14

Shell + common utilities, 41

seq -f"seq -f%g*%%g $1" $1|sh|bc|sort -nu

---

Or alternatively:

Bash + coreutils, 48

eval printf '%s\\n' \$[{1..$1}*{1..$1}]|sort -nu

Constructs a brace expansion inside an arithmetic expansion:

\$[{1..n}*{1..n}] expands to the arithmetic expansions $[1*1] $[1*2] ... $[1*n] ... $[n*n] which are evaluated and passed to printf, which prints one per line, which is piped to sort.

Careful use of quotes, escapes and eval ensure the expansions happen in the required order.

---

Or alternatively:

Pure Bash, 60

eval a=($(eval echo [\$[{1..$1}*{1..$1}\]]=1))
echo ${!a[@]}

Answer 15

J, 21 20 bytes

Thanks to @Zgarb for -1 byte!

/:~@~.@,@(1*/~@:+i.)

My first J answer! Golfing tips are appreciated, if there is something to golf.

This is a monadic function; we take the outer product by multiplication of the list 1..input with itself, flatten, take unique elements, and sort.

Answer 16

Kotlin, 70 bytes

val a={i:Int->(1..i).flatMap{(1..i).map{j->it*j}}.distinct().sorted()}

Ungolfed version:

val a: (Int) -> List<Int> = { 
    i -> (1..i).flatMap{ j -> (1..i).map{ k -> j * k } }.distinct().sorted()
}

Test it with:

fun main(args: Array<String>) {
    for(i in 1..12) {
        println(a(i))
    }
}

Answer 17

Minkolang 0.14, 25 22 18 bytes

I remembered that I very conveniently implemented Cartesian products before this question was posted!

1nLI20P[x*1R]sS$N.

Try it here. (Outputs in reverse order.)

Explanation

1                     Push a 1 onto the stack
 n                    Take number from input (n)
  L                   Pushes 1,2,...,n onto the stack
   I                  Pushes length of stack so 0P knows how many items to pop
    2                 Pushes 2 (the number of repeats)
     0P               Essentially does itertools.product(range(1,n+1), 2)
       [              Open for loop that repeats n^2 times (0P puts this on the stack)
        x             Dump (I know each product has exactly two numbers
         *            Multiply
          1R          Rotate 1 step to the right
            ]         Close for loop
             s        Sort
              S       Remove duplicates ("set")
               $N.    Output whole stack as numbers and stop.

Answer 18

Pyth, 10

S{m*Fd^SQ2

Try it Online or run a Test Suite

Answer 19

TeaScript, 37 35 chars; 40 bytes

Saved 2 bytes thanks to @Downgoat

TeaScript is JavaScript for golfing.

(b+r(1,+x¬)ßam(z=>z*l±s`,`.u¡s»l-i)

Try it online!

Ungolfed and explanation

(b+r(1,+x+1)m(#am(z=>z*l)))s(',').u()s(#l-i)
              // Implicit: x = input number
r(1,+x+1)     // Generate a range of integers from 1 to x.
m(#           // Map each item "l" in this range "a" to:
 am(z=>       //  a, with each item "z" mapped to
  z*l))       //   z * l.
(b+      )    // Parse this as a string by adding it to an empty string.
s(',')        // Split the string at commas, flattening the list.
.u()          // Take only the unique items from the result.
s(#l-i)       // Sort by subtraction; the default sort sorts 10, 12, 100, etc. before 2.
              // Implicit: output last expression

Answer 20

JavaScript (ES6), 92 90 bytes

n=>eval(`for(r=[],a=n;a;a--)for(b=n;b;)~r.indexOf(x=a*b--)||r.push(x);r.sort((a,b)=>a-b)`)

Explanation

n=>eval(`                 // use eval to remove need for return keyword
  for(r=[],a=n;a;a--)     // iterate for each number a
    for(b=n;b;)           // iterate for each number b
      ~r.indexOf(x=a*b--) // check if it is already in the list, x = value
      ||r.push(x);        // add the result
  r.sort((a,b)=>a-b)      // sort the results by ascending value
                          // implicit: return r
`)

Test

N = <input type="number" oninput="result.innerHTML=(

n=>eval(`for(r=[],a=n;a;a--)for(b=n;b;)~r.indexOf(x=a*b--)||r.push(x);r.sort((a,b)=>a-b)`)

)(+this.value)" /><pre id="result"></pre>

Answer 21

Perl 6, 27 bytes

{squish sort 1..$_ X*1..$_} # 27
{unique sort 1..$_ X*1..$_} # 27
{sort unique 1..$_ X*1..$_} # 27

Example usage:

say {squish sort 1..$_ X*1..$_}(3); # (1 2 3 4 6 9)␤

my $code = {squish sort 1..$_ X*1..$_}

for 1..100 -> \N { say $code(N) }

my &code = $code;

say code 4; # (1 2 3 4 6 8 9 12 16)␤

Answer 22

Haskell, 51 bytes

f n=[i|i<-[1..n*n],elem i[a*b|a<-[1..n],b<-[1..n]]]

Pretty boring. Just filters the list [1..n*n] to the elements of the form a*b with a and b in [1..n]. Using filter gives the same length

f n=filter(`elem`[a*b|a<-[1..n],b<-[1..n]])[1..n*n]

I tried for a while to generate the list of products with something more clever like concatMap or mapM, but only got longer results. A more sophisticated check of membership came in at 52 bytes, 1 byte longer, but can perhaps be shortened.

f n=[k|k<-[1..n*n],any(\a->k`mod`a<1&&k<=n*a)[1..n]]

Answer 23

JAVA - 86 Bytes

Set a(int a){Set s=new TreeSet();for(;a>0;a--)for(int b=a;b>0;)s.add(a*b--);return s;}

---

Ungolfed

Set a(int a){
    Set s = new TreeSet();
    for (;a>0;a--){
        for(int b = a;b>0;){
            s.add(a*b--);
        }
    }
    return s;
}

Answer 24

Pyth, 11 bytes

S{sm*RdSdSQ

This is similar to the Julia answer. Thanks to @Maltysen

Answer 25

PHP, 74,73 70bytes

while($i++<$j=$n)while($j)$a[]=$i*$j--;$a=array_unique($a);sort($a);

print_r($a); // Not counted, but to verify the result

Ungolfed:

while($i++<$j=$n)
    while($j)
        $a[]=$i*$j--;

---

Previous:

while(($j=$i++)<$n)for(;$j++<$n;)$a[]=$i*$j;$a=array_unique($a);sort($a);

Not 100% sure what to do with output, but $a contains an array with the corresponding numbers. $n is the number geven via $_GET['n'], with register_globals=1

Answer 26

Jelly, 6 bytes, language postdates challenge

×þµFṢQ

Try it online!

There are so many different ways to do this in 6 bytes that it feels like 5 might be possible. I haven't found a way, though.

Explanation

×þµFṢQ
×þ        Form multiplication (×) table (þ) up to the input
  µ       Fix a parsing ambiguity (µ in Jelly is like parentheses in C)
   F      Flatten the table into a single continuous list
    Ṣ     Sort the elements of the list
     Q    Take the unique elements of the sorted list

Answer 27

Python 3, 57 bytes

r=range(1,n+1);print(sorted({i*j for i in r for j in r}))

Answer 28

Japt, 13 12 11 13 11 bytes

Æõ*XÄÃc â n

Try it online

Answer 29

Python, 124 102 bytes

n=input()
l=[1]
for i in range(1,n+1):
 for j in range(1,n+1):l.append(i*j)
print sorted(list(set(l)))

More pythonic!

Answer 30

C, 96 bytes

i,a[1<<16];main(n){for(scanf("%d",&n);i<n*n;a[~(i%n)*~(i++/n)]="%d ");while(i)printf(a[i--],i);}

This prints the numbers in descending order. Suggestions are welcomed as this looks far from optimal.

Answer 31

JavaScript (ES6), 86 bytes

n=>{n++;a=[];for(j=1;j<n;j++)for(i=1;i<n;i++)if(a.indexOf(i*j)<0)a.push(i*j);return a}

Looking to shorten it (maybe will try nesting loops).

Answer 32

Perl 5, 91 bytes

for my $y (1 .. $ARGV[0]){
    map {$s{$n}++ unless($s{$n=$y*$_}) } ($y .. $ARGV[0])
}
print join(" ", sort {$a<=>$b} keys %s) . "\n";

to be run by passing the argument on the command line. It is quite a few declarations short of running with strictures and warnings.

Answer 33

Perl 5, 67 bytes

for$i(1..($n=pop)){$a{$_*$i}++for 1..$n}map say,sort{$a<=>$b}keys%a

Answer 34

Candy, 22 bytes

Input on stack

R0C(*=bA)bo(~Xe{|A?}x)

Long form:

range1
digit0
cart    # cartesian product of range0 and itself
while
  mult
  popA
  stack2
  pushA  # push products to second stack
endwhile
stack2
order
while    # loop to dedup
  peekA
  pushX
  equal
  if
    else
    pushA
    println
  endif
  XGetsA
endwhile

Answer 35

Perl 5, 83 bytes

Here's a perl version that doesn't do a sort, and doesn't require duplicate removal. I'd like to claim that makes it faster, but it's running time is actually O(n^2.5)

$n=pop;for$i(1..$n*$n){for$j(1+int(($i-1)/$n)..sqrt($i)){if($i%$j==0){say$i;last}}}

A one-character longer and much slower version of this same approach reads as follows:

$n=pop;
for $i (1..$n*$n) {
  for $j (1..$i) {
    if ($i%$j == 0 && $i <= $n*$j && $i >=$ j*$j) {
      say $i;
      last
    }
  }
}

It works by traversing the multiplication table in a strictly ordered fashion.

Answer 36

Prolog (SWI), 94 bytes

As the output only had to be in a reasonable format I've chosen to save 7 bytes by returning the list (which displays it), rather than doing an explicit write.

Code:

p(N,S):-findall(O,between(1,N,O),M),findall(Z,(member(X,M),member(Y,M),Z is X*Y),L),sort(L,S).

Explained:

p(N,S):-findall(O,between(1,N,O),M),                      % Get a list of numbers between 1 and N.
        findall(Z,(member(X,M),member(Y,M),Z is X*Y),L),  % Create a list of the products of the different combinations of elements in the list of numbers between 1 and N. 
        sort(L,S).                                        % Sort and remove doubles

Example:

p(6,L).
L = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 30, 36]

Try it out online here