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, 11 bytes

S{sm*RdSdSQ

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

Answer 2

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 3

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 4

Python 3, 57 bytes

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

Answer 5

Factor + math.matrices, 43 bytes

[ [1,b] dup outer [ ] gather natural-sort ]

Try it online!

Explanation

             ! 3
[1,b]        ! { 1 2 3 }
dup          ! { 1 2 3 } { 1 2 3 }
outer        ! { { 1 2 3 } { 2 4 6 } { 3 6 9 } }
[ ] gather   ! { 1 2 3 4 6 9 }
natural-sort ! { 1 2 3 4 6 9 }

Answer 6

Arturo, 52 bytes

$[n][sort unique flatten map 1..n'x->map x..n=>[x*]]

Try it

Answer 7

Japt, 13 12 11 13 11 8 7 bytes

õ ï* Íâ

Try it

õ ï* Íâ     :Implicit input of integer U
õ           :Range [1,U]
  ï         :Cartesian product with itself
   *        :Reduce each pair by multiplication
     Í      :Sort
      â     :Deduplicate

Answer 8

Thunno 2, 5 bytes

Ṗ€pUṠ

Try it online!

Explanation

Ṗ€pUṠ  # Implicit input
Ṗ      # Cartesian product
 €p    # Product of each
   U   # Uniquify the list
    Ṡ  # And sort it
       # Implicit output

Answer 9

Google Sheets, 52 bytes

=SORT(UNIQUE(TOCOL(MAKEARRAY(N,N,LAMBDA(i,j,i*j)))))

Answer 10

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 11

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 12

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 13

Perl 5, 67 bytes

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

Answer 14

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 15

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 16

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

Answer 17

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 18

Kamilalisp, 29 bytes

⊼∘⊙∘∊∘[$(⌼ *) #0 #0]∘$(+ 1)∘⍳

Attempt This Online!

Answer 19

jq, 34 characters

[range(1;.+1)*range(1;.+1)]|unique

Sample run:

bash-5.2$ jq --compact-output '[range(1;.+1)*range(1;.+1)]|unique' <<< 5
[1,2,3,4,5,6,8,9,10,12,15,16,20,25]

(range() not generates array — “The numbers are produced as separate outputs.” Found no way to multiply a range's output by itself.)

Try it online!

Answer 20

Swift, 146 137 133 87 bytes

var t={n in Set((1...n).map{i in(1...n).map{(i,$0)}}.joined().map{$0.0*$0.1}).sorted()}

To run, paste this into a playground or the REPL and call t(_:).

Here's an expanded version:

func table(n: Int) -> [[Int]] {
   let range = 1...n

   let combos = range.map { i in
      range.map { j in
         (i, j)
      }
   }.joined()

   let products = combos.map { combo in
      combo.0 * combo.1
   }

   let uniques = Set(products)
   let sorted = uniques.sorted()
   return sorted
}

Let's run through this step by step. We'll assume that n is 4.

First, we create a closed range containing all the numbers from 1 to n, inclusive. So, range is set to 1...4. (In the golfed version, it's more efficient to just create the range twice.)

Now we map over range twice, one map inside the other. This effectively creates a nested array containing every permutation of two numbers within the range 1...n. We then join these arrays to remove the nesting. For our example, this sets combos to

[
   (1, 1), (1, 2), (1, 3), (1, 4),
   (2, 1), (2, 2), (2, 3), (2, 4),
   (3, 1), (3, 2), (3, 3), (3, 4),
   (4, 1), (4, 2), (4, 3), (4, 4)
]

(In actuality, it's a FlattenSequence instead of an Array, but that doesn't matter for what we're going to do with it.)

Next, we map over combos, returning the results of multiplying each tuple's elements together. (Using tuples instead of more arrays saves 2 bytes due to the shorter element access syntax.) This sets products to

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

We then create a Set from this array. Sets are unordered, and can only contain one of each item. This enables us to concisely remove duplicate products, at the cost of losing the order of the products. For all intents and purposes, this sets uniques to

[1, 2, 3, 4, 6, 8, 9, 12, 16].shuffled()

Finally, we call sorted() on uniques to get our ordering back, and return the result, which is

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

By default, sorted() does the same thing as sorted(by: <), which sorts in increasing order.

Answer 21

Scala, 57 bytes

Golfed version. Attempt This Online!

n=>(1 to n).flatMap(i=>(1 to n).map(i*_)).distinct.sorted

Ungolfed version. Attempt This Online!

def f(n: Int): Array[Int] = {
    // Construct a Range from 1 to the input
    val x = 1 to n

    // Compute the outer product of x with itself
    val o = for {
      i <- x
      j <- x
    } yield i * j

    // Get the unique elements and sort them
    o.distinct.sorted.toArray
}

Answer 22

Perl 5 -a, 61 bytes

map{//;map$a{$'*$_}++,1.."@F"}1..$_;say for sort{$a-$b}keys%a

Try it online!