Pseudofactorial

39

4

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

Tony Ruth

Posted 2016-06-09T20:19:47.310

Reputation: 651

6I'm not sure I understand why 2 and 6 were removed from the list of multiples. Can please you clarify the rules? – Maltysen – 2016-06-09T20:23:37.080

2@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. – Tony Ruth – 2016-06-09T20:26:39.930

@TonyRuth ohh i see now, thanks. – Maltysen – 2016-06-09T20:27:21.630

2https://oeis.org/A003418 – Neil – 2016-06-10T00:19:10.873

4Welcome to Programming Puzzles & Code Golf! This is a nice first challenge! – Alex A. – 2016-06-10T00:40:52.120

1Your first challenge got to the top of HNQ. Nice! – Daniel M. – 2016-06-10T00:56:11.300

Thanks, I've never really asked many questions on stack exchange, tried more to answer, but this came up in a puzzle. What is HNQ? – Tony Ruth – 2016-06-10T00:59:26.707

Hot Network Questions. – Neil – 2016-06-10T08:34:41.980

Answers

20

Dyalog APL, 3 bytes

∧/⍳

APL beats Jelly

1 though argument

∧/ LCM across

Adám

Posted 2016-06-09T20:19:47.310

Reputation: 37 779

10That interrobang is so sexy. – shooqie – 2016-06-11T07:17:40.220

1O man you beat Dennis... – Mama Fun Roll – 2016-06-12T04:29:34.723

1Impressive, but how are these 3 bytes? – ceased to turn counterclockwis – 2016-06-12T16:13:06.047

2https://en.wikipedia.org/wiki/APL_(codepage) – Leaky Nun – 2016-06-13T16:57:14.347

10

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.

Dennis

Posted 2016-06-09T20:19:47.310

Reputation: 196 637

8

C (with x86), 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 optimizations on (in debug-mode, it outputs 421).

anatolyg

Posted 2016-06-09T20:19:47.310

Reputation: 10 719

How do you get away with not declaring the type of n, k, b,and t? – Tony Ruth – 2016-06-09T23:49:48.867

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; {...} – anatolyg – 2016-06-09T23:54:32.933

if you're taking advantage of a calling convention then this should really be marked "C (cdecl)" rather than just "C" – Steve Cox – 2016-06-10T20:32:56.690

@SteveCox Both cdecl and stdcall use the same method for return-value, so I guess x86 is enough – anatolyg – 2016-06-13T07:04:10.047

7

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.

nimi

Posted 2016-06-09T20:19:47.310

Reputation: 34 639

6

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.

Dennis

Posted 2016-06-09T20:19:47.310

Reputation: 196 637

1Without 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). – Bakuriu – 2016-06-10T12:02:31.147

6

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

xnor

Posted 2016-06-09T20:19:47.310

Reputation: 115 687

5

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

Luis Mendo

Posted 2016-06-09T20:19:47.310

Reputation: 87 464

5

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

miles

Posted 2016-06-09T20:19:47.310

Reputation: 15 654

4

Mathematica, 13 bytes

LCM@@Range@#&

Leaky Nun

Posted 2016-06-09T20:19:47.310

Reputation: 45 011

isn't this equivalent to just composing LCM and Range with @*? – Maltysen – 2016-06-10T00:04:36.430

1LCM 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. – miles – 2016-06-10T00:30:06.253

3

Julia, 11 bytes

!n=lcm(1:n)

Try it online!

Dennis

Posted 2016-06-09T20:19:47.310

Reputation: 196 637

3

Pyth - 8 bytes

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

f!s%LTSQ

Test Suite.

Maltysen

Posted 2016-06-09T20:19:47.310

Reputation: 25 023

3

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.

Suever

Posted 2016-06-09T20:19:47.310

Reputation: 10 257

1So lcm in Octave accepts more than 2 inputs! Interesting – Luis Mendo – 2016-06-09T21:00:10.410

@LuisMendo Yup 2+ – Suever – 2016-06-09T21:00:29.820

3

MATLAB, 49 bytes

@(x)find(~any(bsxfun(@rem,1:prod(1:x),(1:x)')),1)

Suever

Posted 2016-06-09T20:19:47.310

Reputation: 10 257

+1 for bsxfun – flawr – 2016-06-11T12:07:11.777

3

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

Brad Gilbert b2gills

Posted 2016-06-09T20:19:47.310

Reputation: 12 713

https://ideone.com/gR4SK5 – Brad Gilbert b2gills – 2016-06-12T19:14:42.967

2

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)

Quill

Posted 2016-06-09T20:19:47.310

Reputation: 576

b?g(b,a%b):a saves a byte. – Neil – 2016-06-10T08:36:16.567

y*++i/g(y,i) saves some more bytes. – Neil – 2016-06-10T08:37:12.383

1

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

Titus

Posted 2016-06-09T20:19:47.310

Reputation: 13 814

1

Japt, 10 bytes

No LCM built-in.

@õ e!vX}a1

Try it

Shaggy

Posted 2016-06-09T20:19:47.310

Reputation: 24 623

1

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

Emigna

Posted 2016-06-09T20:19:47.310

Reputation: 50 798

1

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

El'endia Starman

Posted 2016-06-09T20:19:47.310

Reputation: 14 504

1

Ruby, 25 bytes

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

Ruby, 25 bytes

g=->n{n<1?1:a[n-1].lcm n}

Peter Kagey

Posted 2016-06-09T20:19:47.310

Reputation: 2 789

1Hello, and welcome to PPCG! Great first post! You don't have to name your function, so you can remove g=. – NoOneIsHere – 2016-06-10T23:39:10.847

Anonymous functions are allowed. – Erik the Outgolfer – 2016-06-11T11:31:53.790

1

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.

Timtech

Posted 2016-06-09T20:19:47.310

Reputation: 12 038

0

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

steenbergh

Posted 2016-06-09T20:19:47.310

Reputation: 7 772

0

AWK, 42 bytes

{for(x=n=1;n<=$1;)if(x%n++){x++;n=1}$0=x}1

Command line usage:

awk '{for(x=n=2;n<=$1;)if(x%n++){x++;n=2}$0=x}1' <<< NUM

I didn't see an AWK solution and a duplicate of the question just got posted yesterday, so I thought I'd throw this together. It's rather slow solving for 19 or larger on my box, but it works.

Robert Benson

Posted 2016-06-09T20:19:47.310

Reputation: 1 339

0

Axiom, 35 bytes

f(x)==reduce(lcm,[i for i in 1..x])

test code and results

(25) -> [[i,f(i)] for i in [1,6,19,22,30]]
   (25)  [[1,1],[6,60],[19,232792560],[22,232792560],[30,2329089562800]]
                                                  Type: List List Integer

i just make the solution of Find the smallest positive integer which has all integers from 1 to n as factors becouse you say it is douplicate i post it here

RosLuP

Posted 2016-06-09T20:19:47.310

Reputation: 3 036

0

Pari/GP, 14 bytes

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

Try it online!

alephalpha

Posted 2016-06-09T20:19:47.310

Reputation: 23 988

0

8th, 23 bytes

Code

1 ' lcm rot 2 swap loop

This code leaves resulting pseudofactorial on TOS

Usage and example

ok> 7 1 ' lcm rot 2 swap loop .
420

Or more clearly

ok> : pseudofact 1 ' n:lcm rot 2 swap loop ;

ok> 7 pseudofact .
420

Chaos Manor

Posted 2016-06-09T20:19:47.310

Reputation: 521

0

Pyke, 3 bytes, noncompeting

S.L

Try it here!

S   - range(1, input+1)
 .L - lowest_common_multiple(^)

Blue

Posted 2016-06-09T20:19:47.310

Reputation: 26 661

0

Hoon, 67 bytes

|*
*
(roll (gulf 1 +<) |=({a/@ b/_1} (div (mul a b) d:(egcd a b))))

Create the list [1..n], fold over the list with lcm. Unfortunately, the Hoon stdlib doesn't have a pre-built one I can use :/

RenderSettings

Posted 2016-06-09T20:19:47.310

Reputation: 620

0

, 7 chars / 9 bytes

Мū…⩤⁽1ï

Try it here (ES6 only).

Just a LCM of inclusive range from 1 to input.

Mama Fun Roll

Posted 2016-06-09T20:19:47.310

Reputation: 7 234