# Sort the unique numbers in a multiplication table

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]
• So basically, the code returns a list of numbers in the multiplication table specified by N, except any number cannot be repeated? – TanMath Nov 28 '15 at 5:27
• How big can N be? – xsot Nov 28 '15 at 7:39
• @xsot You can assume N*N will be less than your language's maximum usual int value (probably 2^31-1) – Calvin's Hobbies Nov 28 '15 at 7:42
• So essentially this is 1-n and non primes up to n^2. – gregsdennis Nov 30 '15 at 2:28
• @gregsdennis No. There are plenty of composites not present. e.g. 91, 92, 93, 94, 95, 96 for N = 10. – Calvin's Hobbies Nov 30 '15 at 2:44

# 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.

• @FryAmTheEggman Input 5 already needs sorting, otherwise the 10 and 9 in the output are out of order. – Reto Koradi Nov 28 '15 at 16:50
• darn keep on forgetting about that splatting on M. +1 – Maltysen Nov 29 '15 at 21:59

# 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.

• The set(...) can just be a set comp {...}. Also, functions are allowed by default here, so you can just write lambda n:.... – xnor Nov 28 '15 at 7:03
• Thanks for reminding me about set comprehension, I completely forgot it existed. – xsot Nov 28 '15 at 7:09
• I can't see a better way to do this, best I see with recursion is 56: f=lambda n:n*[0]and sorted(set(range(n,n*n+n,n)+f(n-1))). – xnor Nov 28 '15 at 7:22

# 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!

# CJam, 14 12 bytes

{)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. • For the same length, {2m*::)::*_&$}, {)2m*::*_&$0-} – Peter Taylor Nov 28 '15 at 7:50 • How about this for two bytes less :) {,:)_ff*:|$} – Martin Ender Nov 28 '15 at 8:29
• Another way: {)2m*::*0^$} – aditsu quit because SE is EVIL Nov 28 '15 at 9:01 # Octave, 22 bytes @(n)unique((a=1:n)'*a) # 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 # MATLAB, 24 bytes @(n)unique((1:n)'*(1:n)) • Good one! Soon it will be possible to do it in 7 or 8 bytes... :-) – Luis Mendo Nov 29 '15 at 23:35 • Oooh, nice! :-) – Stewie Griffin Nov 30 '15 at 5:21 • @Luis have you tried this one in MATL? – Stewie Griffin Nov 30 '15 at 5:28 • I don't have much time now to read the whole challenge, but seeing your Matlab code it looks like it could be done with MATL – Luis Mendo Nov 30 '15 at 10:32 ## 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). • I was waiting for a *sh answer. :D – Addison Crump Nov 28 '15 at 16:26 • Relevant bash tip. Seems to apply to the Z shell as well. – Dennis Nov 28 '15 at 16:33 • – Digital Trauma Nov 28 '15 at 21:49 # 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] # 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. # Mathematica, 25 bytes Union@@Array[1##&,{#,#}]& # 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 ## 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.

# Pyth, 10

S{m*Fd^SQ2

Try it Online or run a Test Suite

## Minkolang 0.14, 2522 18 bytes

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

# 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.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>

## 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) }

# 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;){
}
}
return s;
}

## Pyth, 11 bytes

S{sm*RdSdSQ

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

# 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

# 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
• You can just use r instead of A.r for generating ranges – Downgoat Nov 28 '15 at 19:28
• Sure this is 35 bytes? I get 35 chars or 40 bytes. – manatwork Dec 1 '15 at 13:43
• @manatwork This would be 35 bytes in the ISO/IEC_8859-1 encoding format. But I'm not sure that TeaScript supports that encoding, so I'll change it to 40 bytes for now. – ETHproductions Dec 2 '15 at 3:15

# 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.

# 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).

# 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.

## 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!

• This is actually 123 bytes, not 124. But you can save a few bytes by using only a single space per indentation level rather than 4. – Alex A. Nov 28 '15 at 6:56
• You can also put l.append(i*j) on the same line as the if conditional. I think it ends up being 102 bytes altogether. – El'endia Starman Nov 28 '15 at 6:57
• And use += instead of append. – Kartik Nov 28 '15 at 8:11
• @El'endiaStarman edited, thanks! – TanMath Nov 28 '15 at 8:13
• One relatively minor issue: list(set(l)) is not guaranteed to be sorted. – El'endia Starman Nov 28 '15 at 8:40

# Perl 5, 67 bytes

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