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

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 10

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 11

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 12

Perl 5, 67 bytes

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

Answer 13

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 14

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 15

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 16

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 17

Kamilalisp, 29 bytes

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

Attempt This Online!

Answer 18

Swift, 146 137 133 bytes

extension Collection{var c:[[Element]]{isEmpty ?[]:map{[first!,$0]}+dropFirst().c}}
var t={Set((1...$0).c.map{$0[0]*$0[1]}).sorted()}

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

Here's an expanded version:

extension Collection<Int> {
    func combos() -> [[Int]] {
        if isEmpty { return [] }

        let partialCombos = map { [first!, $0] }
        return partialCombos + dropFirst().combos()
    }
}

func table(n: Int) -> [Int] {
    let combos = (1...n).combos()
    let products = combos.map { $0[0] * $0[1] }
    let uniqueProducts = Set(products)
    return uniqueProducts.sorted()
}

Let's look at combos() first.

1. First, we check if self is empty; if so, we just return an empty array.
2. We then call map to transform it into an array of two-element arrays, each starting with self.first.
3. We call combos() again on the result of self.dropFirst(), before returning the concatenation of that with partialCombos.

This effectively creates an array containing all the possible combinations of the provided elements. So, for example, the result of calling (1...4).combos() would be:

[[1, 1], [1, 2], [1, 3], [1, 4], [2, 2], [2, 3], [2, 4], [3, 3], [3, 4], [4, 4]]

Now for table(n:). We'll pretend that n is 4 for purposes of demonstration,

1. First, we create a closed range from 1 to 4 and call combos() on it. The result of this is shown above.

2. We then map each array in combos to the product of its elements – so, for example, [2, 3] would be mapped to 6. This results in:

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

3. We initialize a Set from this mapping. Sets in Swift are unordered, and can only contain one of each element. So, for all intents and purposes, the result of this is:

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

   Notice that the duplicate 4 has been removed. Most duplicates are the result of multiplying the same two numbers in a different order, which combos() already dealt with, so the effect of this is minimal, but nonetheless necessary.

4. Finally, we call sorted() on the set. Calling sorted() without an argument is equivalent to calling sorted(by: <), which sorts by increasing order.

Extra Notes

• The combo-producing logic needs to be separated from the rest in order for recursion to work. Figuring out how to do this without recursion would probably shave off a huge amount of bytes.
• Extending Collection<Int> saved a few bytes by removing the need for a bulky function signature.
• I need to extend the more generic Collection instead of something like ClosedRange because a whole bunch of type checking fails if I don't.
• Using a computed property instead of a function saved quite a few bytes here and there.
• The space before the ? in the ternary conditional is required to prevent Swift from trying to optional-chain something that isn't Optional. The space afterward isn't needed, which is a weird exception to Swift's operator whitespace rules, but if it saves me a byte, I'll take it.
• I have to use e.first! instead of e[0] to make the type checker happy. I don't know why.
• Assigning a closure to a variable saved a total of 13 bytes over using a proper function (primarily thanks to type inference), with the added benefit that there are no argument labels when calling it.
• Multiplying the array elements by hand instead of calling reduce(_:_:) saved 3 bytes.