36
\$\begingroup\$

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

52 Answers 52

13
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ @FryAmTheEggman Input 5 already needs sorting, otherwise the 10 and 9 in the output are out of order. \$\endgroup\$ Nov 28, 2015 at 16:50
  • \$\begingroup\$ darn keep on forgetting about that splatting on M. +1 \$\endgroup\$
    – Maltysen
    Nov 29, 2015 at 21:59
13
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ The set(...) can just be a set comp {...}. Also, functions are allowed by default here, so you can just write lambda n:.... \$\endgroup\$
    – xnor
    Nov 28, 2015 at 7:03
  • \$\begingroup\$ Thanks for reminding me about set comprehension, I completely forgot it existed. \$\endgroup\$
    – xsot
    Nov 28, 2015 at 7:09
  • \$\begingroup\$ 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))). \$\endgroup\$
    – xnor
    Nov 28, 2015 at 7:22
12
\$\begingroup\$

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!

\$\endgroup\$
0
7
\$\begingroup\$

Octave, 22 bytes

@(n)unique((a=1:n)'*a)
\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
0
7
\$\begingroup\$

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.
\$\endgroup\$
3
  • \$\begingroup\$ For the same length, {2m*::)::*_&$}, {)2m*::*_&$0-} \$\endgroup\$ Nov 28, 2015 at 7:50
  • 2
    \$\begingroup\$ How about this for two bytes less :) {,:)_ff*:|$} \$\endgroup\$ Nov 28, 2015 at 8:29
  • 1
    \$\begingroup\$ Another way: {)2m*::*0^$} \$\endgroup\$ Nov 28, 2015 at 9:01
4
\$\begingroup\$

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.

\$\endgroup\$
1
4
\$\begingroup\$

MATLAB, 24 bytes

@(n)unique((1:n)'*(1:n))
\$\endgroup\$
4
  • \$\begingroup\$ Good one! Soon it will be possible to do it in 7 or 8 bytes... :-) \$\endgroup\$
    – Luis Mendo
    Nov 29, 2015 at 23:35
  • \$\begingroup\$ Oooh, nice! :-) \$\endgroup\$ Nov 30, 2015 at 5:21
  • \$\begingroup\$ @Luis have you tried this one in MATL? \$\endgroup\$ Nov 30, 2015 at 5:28
  • \$\begingroup\$ 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 \$\endgroup\$
    – Luis Mendo
    Nov 30, 2015 at 10:32
4
\$\begingroup\$

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

\$\endgroup\$
3
4
\$\begingroup\$

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]
\$\endgroup\$
4
\$\begingroup\$

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[@]}
\$\endgroup\$
4
\$\begingroup\$

Husk, 6 bytes

OumΠπ2

Try it online!

Explanation

OumΠπ2
    π2  cartesian square
  mΠ    map product
 u      unique
O       sort
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
0
3
\$\begingroup\$

JavaScript (Node.js), 69 bytes

n=>[...a=Array(i=n*n)].map(x=>a[q=~(--i%n)*~(i/n)]=q)&&a.filter(x=>x)

Try it online!

JavaScript (Node.js), 76 bytes

n=>[...Array(n*n)].flatMap((_,i,x)=>x.every((_,j)=>~(j/n)*~(j%n)+~i)?[]:i+1)

Try it online!

No recursion like other answers

\$\endgroup\$
2
\$\begingroup\$

Mathematica, 25 bytes

Union@@Array[1##&,{#,#}]&
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
0
2
\$\begingroup\$

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))
    }
}
\$\endgroup\$
2
\$\begingroup\$

Pyt, 7 bytes

řĐɐ*ƑỤş

Try it online!

ř           implicit input (n); push [1,2,...,n]
 Đ          duplicate
  ɐ*        generate multiplication table
    Ƒ       flatten array
     Ụ      get unique elements
      ş     sort in ascending order; implicit print
\$\endgroup\$
2
\$\begingroup\$

Thunno, \$ 12 \log_{256}(96) \approx \$ 9.88 bytes

R1+DZ!.PZU

Explanation

R1+DZ!.PZUz:  # Implicit input                    Example (n=5)
R1+           # [1..input]                        [1, 2, 3, 4, 5]
   DZ!        # Cartesian product with itself     [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5]]
      .P      # Product of each inner list        [1, 2, 3, 4, 5, 2, 4, 6, 8, 10, 3, 6, 9, 12, 15, 4, 8, 12, 16, 20, 5, 10, 15, 20, 25]
        ZU    # Uniquified                        [1, 2, 3, 4, 5, 6, 8, 10, 9, 12, 15, 16, 20, 25]
          z:  # And sorted                        [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 20, 25]
              # Implicit output

Screenshot

Screenshot

\$\endgroup\$
2
\$\begingroup\$

Vyxal, 7 bytes

ɾẊƛΠ;Us

Try it Online!

\$\endgroup\$
1
  • \$\begingroup\$ Try it Online! for 5 or 4.25 bytes \$\endgroup\$
    – lyxal
    Jul 20, 2023 at 1:15
2
\$\begingroup\$

Jelly, 5 bytes

Ṭẋ)ST

Try it online!

  )      For each x in 1 .. n:
Ṭ        Create a list containing 1 at index x and 0s before it,
 ẋ       and repeat it x times.
   S     Sum the results element-wise,
    T    and yield the indices of non-zeros in the result.
\$\endgroup\$
2
\$\begingroup\$

Brachylog, 9 bytes

⟦₁⟨∋×∋⟩ᵘo

Try it online!

Explanation

⟦₁⟨∋×∋⟩ᵘo
⟦₁        Range from 1 to input number, inclusive
      ᵘ   Get all unique outputs of this predicate:
  ∋         Pick a number from that range
    ∋       Pick another number from that range
 ⟨ ×  ⟩      Multiply them together
       o  Sort the resulting list
\$\endgroup\$
1
\$\begingroup\$

Pyth, 10

S{m*Fd^SQ2

Try it Online or run a Test Suite

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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>

\$\endgroup\$
1
\$\begingroup\$

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)␤
\$\endgroup\$
1
\$\begingroup\$

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]]
\$\endgroup\$
1
  • \$\begingroup\$ You can save 3 bytes by using (*)<$>..<*>.. like this \$\endgroup\$ Jan 15, 2018 at 18:54
1
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.