47
\$\begingroup\$

There is a rather curious number which shows up sometimes in math problems or riddles. The pseudofactorial(N) is the least (i.e. lowest) common multiple of the numbers 1 through N; in other words, it's the lowest number which has all numbers from 1 through N as factors.

For instance pseudofactorial(7) = 3 * 4 * 5 * 7, which is the same as 7! except that 2 and 6 have been removed because they are contained in other terms.

Write a program to calculate pseudofactorial(N) and as always, shortest code wins.

Here is a short list for your use. More test cases can be found in the OEIS under A003418.

Factorial:

  1. 1
  2. 2
  3. 6
  4. 24
  5. 120
  6. 720
  7. 5040

Pseudofactorial:

  1. 1
  2. 2
  3. 6
  4. 12
  5. 60
  6. 60
  7. 420
\$\endgroup\$
7
  • 7
    \$\begingroup\$ I'm not sure I understand why 2 and 6 were removed from the list of multiples. Can please you clarify the rules? \$\endgroup\$ Commented Jun 9, 2016 at 20:23
  • 4
    \$\begingroup\$ @Mattysen, psuedofactorial(N) is the smallest number which has the numbers 1 through N as factors (The least common multiple of those numbers). That is the technical definition, but the way I wrote it was somewhat suggestive that it is similar to a factorial. \$\endgroup\$ Commented Jun 9, 2016 at 20:26
  • 2
    \$\begingroup\$ oeis.org/A003418 \$\endgroup\$ Commented Jun 10, 2016 at 0:19
  • 4
    \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! This is a nice first challenge! \$\endgroup\$ Commented Jun 10, 2016 at 0:40
  • 1
    \$\begingroup\$ Your first challenge got to the top of HNQ. Nice! \$\endgroup\$ Commented Jun 10, 2016 at 0:56

45 Answers 45

22
\$\begingroup\$

APL (dzaima/APL), 3 2 bytes

∧⍳ 

Try it online!

APL beats Jelly

1 though argument

LCM across

\$\endgroup\$
4
  • 11
    \$\begingroup\$ That interrobang is so sexy. \$\endgroup\$ Commented Jun 11, 2016 at 7:17
  • 1
    \$\begingroup\$ O man you beat Dennis... \$\endgroup\$ Commented Jun 12, 2016 at 4:29
  • 2
    \$\begingroup\$ Impressive, but how are these 3 bytes? \$\endgroup\$ Commented Jun 12, 2016 at 16:13
  • 2
    \$\begingroup\$ en.wikipedia.org/wiki/APL_(codepage) \$\endgroup\$ Commented Jun 13, 2016 at 16:57
11
\$\begingroup\$

Jelly, 4 bytes

Ræl/ 

Try it online! or verify all test cases.

How it works

Ræl/ Main link. Input: n R Range; yield [1, ..., n]. / Reduce the range... æl by LCM. 
\$\endgroup\$
0
8
\$\begingroup\$

C (x86-64 gcc -O1), 52 bytes

d(n,k,b,t){for(b=k=1;b;++k)for(t=n,b=0;t;b+=k%t--);} 

Checks numbers from 1 upwards. For each number, divides it by all numbers from n down to 1, and sums the remainders. Stops when the sum is 0.

Usage:

main() { printf("%d\n", d(7)); // outputs 420 } 

It's not obvious how it returns a value (there is no return statement).

The calling convention for x86 says that the function must return its value in the eax register. Conveniently, the division instruction idiv expects its input in eax, and outputs the result in eax (quotient) and edx (remainder). The last iteration divides k by 1, so eax will contain the right value when the function exits.

This only works with gcc and -O1 optimization option (otherwise, it outputs different results — usually 0 or random-looking numbers, but sometimes 421, while the correct answer is 420).

Try it with Compiler Explorer

\$\endgroup\$
7
  • \$\begingroup\$ How do you get away with not declaring the type of n, k, b,and t? \$\endgroup\$ Commented Jun 9, 2016 at 23:49
  • \$\begingroup\$ C has the default-int rule - all omitted types are int by default (including the return value). It works for function arguments if they are declared using the so-called "old-style" syntax. The declaration with explicitly defined types would be int d(n,k,b,t) int n,k,b,t; {...} \$\endgroup\$ Commented Jun 9, 2016 at 23:54
  • \$\begingroup\$ if you're taking advantage of a calling convention then this should really be marked "C (cdecl)" rather than just "C" \$\endgroup\$ Commented Jun 10, 2016 at 20:32
  • \$\begingroup\$ @SteveCox Both cdecl and stdcall use the same method for return-value, so I guess x86 is enough \$\endgroup\$ Commented Jun 13, 2016 at 7:04
  • 1
    \$\begingroup\$ @Deadcode It works in all gcc versions (but only with -O1), and in some clang versions. Fortunately, we have Compiler Explorer! I added a link so anyone could check these results. \$\endgroup\$ Commented Mar 30, 2023 at 12:08
7
\$\begingroup\$

Haskell, 20 bytes

f x=foldr1 lcm[1..x] 

Usage example: map f [1..7] -> [1,2,6,12,60,60,420].

The lcm trick in Haskell.

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

Python, 46 bytes

g=lambda n,c=0:n<1or(c%n<1)*c or g(n,c+g(n-1)) 

Looking for the multiple c of g(n-1) directly. I had though before that this method would wrongly find 0 as a multiple of anything, but the or short-circuiting or (c%n<1)*c will skip c==0 as well because 0 is Falsey.


50 bytes:

g=lambda n,i=1:n<1or(i*n%g(n-1)<1)*i*n or g(n,i+1) 

Like Dennis's solution, but as a recursive function. Having computed g(n-1), looks for the smallest multiple i*n of n that's also a multiple of g(n-1). Really slow.

Thanks to Dennis for 4 bytes by looking at multiples of n instead of g(n-1).

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

Python + SymPy, 45 bytes

import sympy lambda n:sympy.lcm(range(1,n+1)) 

Fairly self-explanatory.


Python 2, 57 54 bytes

i=r=input();exec't=r\nwhile r%i:r+=t\ni-=1;'*r;print r 

Test it on Ideone.

How it works

The input is stored in variables i and r.

exec executes the following code r times.

t=r while r%i:r+=t i-=1 

While i varies from r to 1, we add the initial value of r (stored in t) as many times as necessary to r itself to create a multiple of i. The result is, obviously, a multiple of t.

The final value of r is thus a multiple of all integers in the range [1, ..., n], where n is the input.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Without using third party libraries or exec tricks there's a 78 byte solution: from fractions import*;lambda n:reduce(lambda x,y:x*y/gcd(x,y),range(1,n+1),1) Uses the fact that lcm(x,y) = x*y/gcd(x,y). \$\endgroup\$ Commented Jun 10, 2016 at 12:02
  • \$\begingroup\$ use python standard lib math to get 44 bytes. import math;lambda n:math.lcm(*range(1,n+1)) \$\endgroup\$ Commented Aug 22 at 4:54
5
\$\begingroup\$

Julia, 11 bytes

!n=lcm(1:n) 

Try it online!

\$\endgroup\$
5
\$\begingroup\$

J, 9 bytes

[:*./1+i. 

Straight-forward approach. Creates the range of numbers [0, ..., n-1], then adds one to each, and reduce it using the LCM.

Usage

 f =: [:*./1+i. f 7 420 
\$\endgroup\$
5
\$\begingroup\$

MATL, 4 bytes

:&Zm 

Try it online!

Explanation

: % Take input N implicitly. Generate range [1 2 ... N] &Zm % LCM of the numbers in that array. Display implicitly 
\$\endgroup\$
5
\$\begingroup\$

Mathematica, 13 bytes

LCM@@Range@#& 
\$\endgroup\$
2
  • \$\begingroup\$ isn't this equivalent to just composing LCM and Range with @*? \$\endgroup\$ Commented Jun 10, 2016 at 0:04
  • 1
    \$\begingroup\$ LCM operates element-wise on a list, which would be passed by Range, meaning this would just return the lcm(x) for x from 1 through n. Also, there's a missing & that would close the anonymous function. Something like LCM@@Range@#& for 13 bytes would work. \$\endgroup\$ Commented Jun 10, 2016 at 0:30
5
\$\begingroup\$

Regex 🐇 (PCRE2 v10.35+), 60 59 54 52 bytes

^((?*(?=(xx+?)\2*$|)((?=x\2)(x+)\4*(?=\4$))*+x+)x)*$ 

Takes its input in unary, as a string of x characters whose length represents the number. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method.)

Attempt This Online! - PCRE2 v10.40+

The 🐇 output method takes advantage of an aspect of regex that's normally hidden: the backtracking paths that aren't taken. In normal use, all traces of the avenues of potential alternative matches are erased when a final match is found. But in 🐇, they're all taken and counted, allowing a number to be outputted that's larger than the input. For scalar unary input, this provides a strict superset of the power of returning a number via the matched substring or a capture group (either of which can only return values less than or equal to the input), except that there can be no extra state of returning "no match" (in 🐇, that just returns \$0\$).

The limitation of having to work within the space of the input is still present. 🐇 can do combinations of multiplication and addition to yield numbers larger than the input, but it can't do subsequent tests on those results (it can only do tests on intermediate results calculated using capture groups and tail). So for example in this problem, the regex can't just directly search for the smallest number that is divisible by all numbers in the range \$[1,n]\$, because that number is not only larger than the input, it's too large even to be able to emulate using number base arithmetic (and even if that were possible, it would not golf well). So, this regex uses an algorithm different from all of the other answers:

It takes the base prime \$p\$ of every prime power \$p^k\le n\$, and calculates the product of that list of numbers. And because each \$p\$ will occur \$\max \left\{ k \, \middle| \, p^k \le n \right\}\$ times in that list, this product is the same as the product of the prime powers themselves would be, if only the largest from each base prime were included.

The prime power portion is based on my prime powers answer Neil's prime powers answer (which is in turn based on my earliest CGCC answer). In the prime powers challenge, my regex is shorter, but for the purposes of this challenge, his regex (after some extra golfing) allows capturing the smallest prime factor, thus golfing down the overall regex by 1 6 bytes.

^ # tail = N = input number ( # Loop the following: (?* # Non-atomic lookahead: # M = tail, which cycles from N down to 1 (?=(xx+?)\2*$|) # \2 = smallest prime factor of M if M ≥ 2; # otherwise, leave \2 unchanged in PCRE, or # unset in ECMAScript ( (?=x\2) # Keep iterating until tail ≤ \2, and because of # what \2 is, this means at the end of the loop, # either tail == \2 (if M is a prime power) or # tail == 1 (if M is not a prime power) (x+)\4*(?=\4$) # tail = \4 = {largest proper divisor of tail} # = tail / {smallest prime factor of tail} )*+ # Iterate the above as many times as possible, # minimum zero, and lock in the result using a # possessive quantifier. x+ # Multiply number of possible matches by tail ) x # tail -= 1 )* # Loop the above a minimum of 0 times $ # Assert that at the end of the above loop, tail == 0 

This even returns a correct value for \$n=0\$, while the earlier 60 byte version did not (and needed to be extended to 63 bytes to do so).

A list of other answers that return \$f(0)=1\$ correctly, complete at the time of this edit: AWK, Dyalog APL, J, Japt, Julia v0.7+ (but it was v0.6 at the time of posting, and didn't support it then), MATLAB, MATL, Maxima (with functs), Minkolang (1st answer), Nibbles, PHP, Pari/GP, Perl 5, Perl 6, Pyth, Python (with SymPy), Python (with math), Python, QBIC, Rexx, Vyxal. (Not tested: 8th, Axiom, Hoon)

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

Thunno 2, 2 bytes

Try it online!

Explanation

 # Implicit input R # Range [1..input] ŀ # Reduced by LCM # Implicit output 
\$\endgroup\$
3
\$\begingroup\$

Pyth - 8 bytes

Checks all numbers till it finds one that is divisible by [1..N].

f!s%LTSQ 

Test Suite.

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

Octave, 27 bytes

@(x)lcm(1,num2cell(1:x){:}) 

Creates an anonymous function that can be invoked as ans(N).

Online Demo

Explanation

This solution creates a list of all numbers between 1 and x (1:x), converts them to a cell array with num2cell. Then the {:} indexing creates a comma-separated-list which is passed to lcm as multiple input arguments to compute the least common multiple. A 1 is always passed as the first argument to lcm because lcm always needs at least two input arguments.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ So lcm in Octave accepts more than 2 inputs! Interesting \$\endgroup\$ Commented Jun 9, 2016 at 21:00
  • \$\begingroup\$ @LuisMendo Yup 2+ \$\endgroup\$ Commented Jun 9, 2016 at 21:00
3
\$\begingroup\$

MATLAB, 49 bytes

@(x)find(~any(bsxfun(@rem,1:prod(1:x),(1:x)')),1) 
\$\endgroup\$
0
3
\$\begingroup\$

Perl 6, 13 bytes

{[lcm] 1..$_} 

Anonymous code block that creates a Range from 1 to the input (inclusive), and then reduces that with &infix:<lcm>.

Example:

#! /usr/bin/env perl6 use v6.c; my &postfix:<p!> = {[lcm] 1..$_} say 1p!; # 1 say 2p!; # 2 say 3p!; # 6 say 4p!; # 12 say 5p!; # 60 say 6p!; # 60 say 7p!; # 420 say 10000p!; # 5793339670287642968692270879... # the result from this is 4349 digits long 
\$\endgroup\$
1
3
\$\begingroup\$

Arturo, 13 bytes

$=>[[email protected]&] 

Try it

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

Brachylog, 5 bytes

fa~⟦₁ 

Try it online!

Reversed I/O.

 a An affix of f the list of the output's factors ~⟦₁ is [1 .. n]. 

Essentially a specialization of my basic LCM solution f⊇p~d: ranges are duplicate-free, so they don't need to be deduplicated; ranges are ascending, so they don't need to be permuted; ranges are necessarily contiguous prefixes of the list of factors, so can be replaced by the evidently much more performant a.

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

Nibbles, 5.5 bytes

/|,~~+.,@%@ 

Attempt This Online!

/|,~~+.,@%@ /|,~ Find the first positive integer k such that + the sum .,@ for i from 1 to n %@ of k mod i ~ is zero 
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 92 88 80 74 69 bytes:

Thanks @ConorOBrien and @Neil

y=>(g=(a,b)=>b?g(b,a%b):a,[...Array(y)].map((_,i)=>y=y*++i/g(y,i)),y) 
\$\endgroup\$
2
  • \$\begingroup\$ b?g(b,a%b):a saves a byte. \$\endgroup\$ Commented Jun 10, 2016 at 8:36
  • \$\begingroup\$ y*++i/g(y,i) saves some more bytes. \$\endgroup\$ Commented Jun 10, 2016 at 8:37
2
\$\begingroup\$

Ruby, 25 bytes

g=->n{(1..n).reduce :lcm} 

Ruby, 25 bytes

g=->n{n<1?1:a[n-1].lcm n} 
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Hello, and welcome to PPCG! Great first post! You don't have to name your function, so you can remove g=. \$\endgroup\$ Commented Jun 10, 2016 at 23:39
  • \$\begingroup\$ Anonymous functions are allowed. \$\endgroup\$ Commented Jun 11, 2016 at 11:31
2
\$\begingroup\$

Desmos, 16 bytes

f(n)=[1...n].lcm 

Super straightforward

Try It On Desmos!

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

Nim, 52 bytes

import math,sequtils func p[I](n:I):I=lcm toSeq 1..n 

Attempt This Online!

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

05AB1E, 20 bytes

Lpvyi¹LÒN>¢àN>*ˆ}}¯P 

Explanation

Lpv # for each item in isprime(range(1,N)): N=7 -> [0,1,1,0,1,0,1] yi # if prime ¹LÒN>¢ # count occurrences of the prime in the prime-factorization of range(1,N): p=2 -> [0,1,0,2,0,1,0] àN>*ˆ # add max occurrence of that prime multiplied by the prime to global array: N=7 -> [4,3,5,7] }} # end if/loop ¯P # get product of global array 

Try it online

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

Minkolang 0.15, 12 bytes

I have two 12-byte solutions, and have included them both.

1n[i1+4$M]N. 

Try it here!

Explanation

1 Push 1 n Take number from input [ For loop that repeats n times i1+ Push loop counter + 1 4$M Pop b, a and push lcm(a,b) ] Close for loop N. Output as number and stop. 

About as straightforward as it gets.


11nLd[4$M]N. 

Try it here!

Explanation

11 Push two 1s n Take number from input L Pop b, a and push range from a to b, inclusive d Duplicate top of stack (n) [4$M] Pop b, a and push lcm(a,b), n times N. Output as number and stop. 

A third solution can be derived from this: remove a 1 and add a d after the current d. In both cases, the extra number is needed because the for loop runs one too many times, and making it run one less time takes two bytes (1- just before the [).

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

GameMaker Language, 60 bytes

for(b=k=1;b;++k){b=0for(t=argument0;t;b+=k mod t--)}return k 

Based on the logic of anatolyg's answer.

\$\endgroup\$
1
  • \$\begingroup\$ I haven't actually tested this in GameMaker, but as written it almost certainly doesn't work, and needs to return k-1, not k. \$\endgroup\$ Commented Mar 30, 2023 at 0:17
1
\$\begingroup\$

PHP, 61 52 48 bytes

saved 9 bytes thanks to @user59178, 4 bytes by merging the loops.

Recursion in PHP is bulky due to the function key word; so I use iteration.
And with a "small"few tricks, I now even beat Arnauld´s JS.

while(++$k%++$i?$i>$argv[1]?0:$i=1:$k--);echo$k; 

takes input from command line argument. Run with -r.

breakdown

while(++$k%++$i? # loop $i up; if it does not divide $k $i>$argv[1]?0 # break if $i (smallest non-divisor of $k) is larger than input :$i=1 # while not, reset $i and continue loop with incremented $k :$k--); # undo increment while $i divides $k echo$k; # print $k 

ungolfed

That´s actually two loops in one:

while($i<=$argv[1]) # loop while $i (smallest non-divisor of $k) is not larger than input for($k++, # loop $k up from 1 $i=0;$k%++$i<1;); # loop $i up from 1 while it divides $k echo$k; # print $k 

Note: copied from my answer on the duplicate

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

QBIC, 35 32 bytes

This brought me here.

:{p=0[a|~q%b|p=1]]~p=0|_Xq\q=q+1 

Explanation:

: Get cmd line param as number 'a' { Start an infinite DO loop p=0 Sets a flag that shows if divisions failed [a| FOR (b=1; b<=a; b++) ~q%b IF 'q' (which starts at 1 in QBIC) is not cleanly divisible by 'b' |p=1 THEN Set the flag ]] Close the FOR loop and the IF, leave the DO open ~p=0 IF 'q' didn't get flagged |_Xq THEN quit, printing 'q' \q=q+1 ELSE raise 'q', redo [DO Loop implicitly closed by QBIC] 

Here's a version that stops testing q when b doesn't cleanly divide it. Also, the order of testing b's against q is reversed in the assumption that higher b's will be harder to divide by (take 2, 3, 4 for instance: if %2=0, %4 could be !0. Vice versa not so much...).

:{p=0[a,2,-1|~q%b|p=1┘b=2]]~p=0|_Xq\q=q+1 
\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 14 bytes

n->lcm([1..n]) 

Try it online!

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

Japt, 10 bytes

No LCM built-in.

@õ e!vX}a1 

Try it

\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.