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

1
2
1
\$\begingroup\$

Pyth, 11 bytes

S{sm*RdSdSQ

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

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

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

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

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
\$\endgroup\$
3
  • \$\begingroup\$ You can just use r instead of A.r for generating ranges \$\endgroup\$
    – Downgoat
    Nov 28, 2015 at 19:28
  • \$\begingroup\$ Sure this is 35 bytes? I get 35 chars or 40 bytes. \$\endgroup\$
    – manatwork
    Dec 1, 2015 at 13:43
  • \$\begingroup\$ @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. \$\endgroup\$ Dec 2, 2015 at 3:15
1
\$\begingroup\$

Python 3, 57 bytes

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

\$\endgroup\$
6
  • \$\begingroup\$ You're not outputting the result. Wrap the sorted with a print and it'll be fine \$\endgroup\$
    – Blue
    May 23, 2017 at 9:32
  • \$\begingroup\$ I thought that's OK since default behavior of Python CLI is outputting the last command. It's my first CodeGolf, too. \$\endgroup\$
    – ceruleus
    May 23, 2017 at 9:57
  • \$\begingroup\$ By the way, where is the print here: codegolf.stackexchange.com/a/65059/69669 ? \$\endgroup\$
    – ceruleus
    May 23, 2017 at 9:58
  • 1
    \$\begingroup\$ I know this is often confusing for new users but we allow functions as well as full programs. In that case, the line returns a function which can be used. However with what you had, the result wasn't going anywhere. We have a long meta discussion on it which can be found here: codegolf.meta.stackexchange.com/q/2447/32686 \$\endgroup\$
    – Blue
    May 23, 2017 at 10:09
  • \$\begingroup\$ Also, I didn't notice the first time but you've got to do n=in(input()) or r=range(1,int(input())+1) because we don't allow snippets in general. I'm sorry for all this no-fun stuff :( \$\endgroup\$
    – Blue
    May 23, 2017 at 10:13
1
\$\begingroup\$

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

Arturo, 52 bytes

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

Try it

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

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

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

Google Sheets, 52 bytes

=SORT(UNIQUE(TOCOL(MAKEARRAY(N,N,LAMBDA(i,j,i*j)))))
\$\endgroup\$
0
\$\begingroup\$

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

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

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.

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

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!

\$\endgroup\$
8
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – Alex A.
    Nov 28, 2015 at 6:56
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Nov 28, 2015 at 6:57
  • 3
    \$\begingroup\$ And use += instead of append. \$\endgroup\$
    – Kartik
    Nov 28, 2015 at 8:11
  • \$\begingroup\$ @El'endiaStarman edited, thanks! \$\endgroup\$
    – TanMath
    Nov 28, 2015 at 8:13
  • 1
    \$\begingroup\$ One relatively minor issue: list(set(l)) is not guaranteed to be sorted. \$\endgroup\$ Nov 28, 2015 at 8:40
0
\$\begingroup\$

Perl 5, 67 bytes

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

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.

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

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

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

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

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

Kamilalisp, 29 bytes

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

Attempt This Online!

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

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!

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

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.

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

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

Perl 5 -a, 61 bytes

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

Try it online!

\$\endgroup\$
1
2

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.