Pseudofactorial

39

Ada angka yang agak aneh yang terkadang muncul dalam soal matematika atau teka-teki. The pseudofactorial (N) adalah kelipatan umum paling tidak (yaitu terendah) dari angka 1 sampai N; dengan kata lain, itu adalah angka terendah yang memiliki semua angka dari 1 hingga N sebagai faktor.

Misalnya pseudofactorial (7) = 3 * 4 * 5 * 7, yang sama dengan 7! kecuali bahwa 2 dan 6 telah dihapus karena terkandung dalam istilah lain.

Tulis program untuk menghitung pseudofactorial (N) dan seperti biasa, kode terpendek menang.

Berikut adalah daftar singkat untuk Anda gunakan. Lebih banyak kasus uji dapat ditemukan di OEIS di bawah A003418 .

Faktorial:

  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
sumber
6
Saya tidak yakin saya mengerti mengapa 2dan 6dihapus dari daftar kelipatan. Bisakah Anda menjelaskan aturannya?
Maltysen
2
@Mattysen, psuedofactorial (N) adalah angka terkecil yang memiliki angka 1 hingga N sebagai faktor (Kelipatan paling umum dari angka-angka itu). Itu adalah definisi teknis, tetapi cara saya menulisnya agak menunjukkan bahwa itu mirip dengan faktorial.
Tony Ruth
4
Selamat Datang di Programming Puzzles & Code Golf! Ini adalah tantangan pertama yang bagus!
Alex A.
1
Tantangan pertama Anda sampai di puncak HNQ. Bagus!
Daniel M.

Jawaban:

19

Dyalog APL , 3 byte

∧/⍳

APL mengalahkan Jelly

1 meskipun argumen

∧/ LCM di seberang

Adám
sumber
10
Interrobang itu sangat seksi.
shooqie
1
Wahai pria yang mengalahkan Dennis ...
Mama Fun Roll
1
Mengesankan, tapi bagaimana 3 byte ini ?
Berhenti menghidupkan counterclockwis
8

C (dengan x86), 52 byte

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

Cek angka dari 1 ke atas. Untuk setiap angka, bagilah dengan semua angka dari n hingga 1, dan jumlah sisanya. Berhenti ketika jumlahnya 0.

Pemakaian:

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

Tidak jelas bagaimana cara mengembalikan nilai (tidak ada returnpernyataan).

Konvensi panggilan untuk x86 mengatakan bahwa fungsi tersebut harus mengembalikan nilainya dalam eaxregister. Dengan mudah, instruksi divisi idivmengharapkan inputnya masuk eax, dan mengeluarkan hasilnya dalam eax(hasil bagi) dan edx(sisanya). Iterasi terakhir dibagi kdengan 1, jadi eaxakan berisi nilai yang benar ketika fungsi keluar.

Ini hanya berfungsi dengan optimisasi aktif (dalam mode debug, menghasilkan 421).

anatolyg
sumber
Bagaimana Anda lolos dengan tidak menyatakan jenis n, k, b, dan t?
Tony Ruth
C memiliki aturan default-int - semua tipe yang dihilangkan adalah intsecara default (termasuk nilai balik). Ini berfungsi untuk argumen fungsi jika mereka dideklarasikan menggunakan apa yang disebut sintaks "gaya lama". Deklarasi dengan tipe yang didefinisikan secara eksplisit adalahint d(n,k,b,t) int n,k,b,t; {...}
anatolyg
jika Anda memanfaatkan konvensi pemanggilan maka ini harus benar-benar ditandai "C (cdecl)" daripada hanya "C"
Steve Cox
@SteveCox Keduanya cdecldan stdcallmenggunakan metode yang sama untuk nilai-kembali, jadi saya kira x86sudah cukup
anatolyg
7

Haskell, 20 byte

f x=foldr1 lcm[1..x]

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

The lcmtrick dalam Haskell.

nimi
sumber
6

Python + SymPy, 45 byte

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

Cukup jelas.


Python 2, 57 54 byte

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

Uji di Ideone .

Bagaimana itu bekerja

Input disimpan dalam variabel i dan r .

execmengeksekusi kode r kali berikut .

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

Sementara saya bervariasi dari r ke 1 , kami menambahkan nilai awal r (disimpan dalam t ) sebanyak yang diperlukan untuk r itu sendiri untuk membuat kelipatan i . Hasilnya, jelas, kelipatan t .

Nilai akhir r adalah kelipatan dari semua bilangan bulat dalam rentang [1, ..., n] , di mana n adalah input.

Dennis
sumber
1
Tanpa menggunakan pustaka atau exectrik pihak ketiga ada solusi 78 byte: from fractions import*;lambda n:reduce(lambda x,y:x*y/gcd(x,y),range(1,n+1),1) Menggunakan fakta itu lcm(x,y) = x*y/gcd(x,y).
Bakuriu
6

Python, 46 byte

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

Mencari beberapa cdari g(n-1)langsung. Saya pernah sebelumnya bahwa metode ini akan salah menemukan 0 sebagai kelipatan dari apa pun, tetapi orkorsleting atau (c%n<1)*cakan melompat c==0juga karena 0 adalah Falsey.


50 byte:

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

Seperti solusi Dennis , tetapi sebagai fungsi rekursif. Memiliki dihitung g(n-1), terlihat untuk beberapa terkecil i*ndari nitu juga kelipatan g(n-1). Sangat lambat.

Terima kasih kepada Dennis untuk 4 byte dengan melihat kelipatan nalih-alih g(n-1).

Tidak
sumber
5

J, 9 byte

[:*./1+i.

Pendekatan lurus ke depan. Buat kisaran angka [0, ..., n-1], lalu tambahkan satu untuk masing-masing, dan kurangi menggunakan LCM.

Pemakaian

   f =: [:*./1+i.
   f 7
420
mil
sumber
5

MATL , 4 byte

:&Zm

Cobalah online!

Penjelasan

:      % Take input N implicitly. Generate range [1 2 ... N]
&Zm    % LCM of the numbers in that array. Display implicitly
Luis Mendo
sumber
4

Mathematica, 13 byte

LCM@@Range@#&
Biarawati Bocor
sumber
bukankah ini setara dengan hanya menulis LCMdan Rangedengan @*?
Maltysen
1
LCMmengoperasikan elemen-bijaksana pada daftar, yang akan dilewati Range, yang berarti ini hanya akan mengembalikan lcm ( x ) untuk x dari 1 hingga n . Juga, ada yang hilang &yang akan menutup fungsi anonim. Sesuatu seperti LCM@@Range@#&untuk 13 byte akan berfungsi.
mil
3

Julia, 11 byte

!n=lcm(1:n)

Cobalah online!

Dennis
sumber
3

Pyth - 8 byte

Periksa semua angka sampai ditemukan nomor yang dapat dibagi [1..N].

f!s%LTSQ

Test Suite .

Maltysen
sumber
3

Oktaf, 27 byte

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

Membuat fungsi anonim yang dapat dipanggil sebagai ans(N).

Demo online

Penjelasan

Solusi ini membuat daftar semua angka antara 1dan x( 1:x), mengonversinya menjadi array sel num2cell. Kemudian {:}pengindeksan membuat daftar dipisahkan koma yang dilewatkan lcmsebagai argumen input ganda untuk menghitung multiple paling umum. A 1 selalu diteruskan sebagai argumen pertama lcmkarena lcmselalu membutuhkan setidaknya dua argumen input.

Suever
sumber
1
Jadi, lcmdalam Oktaf menerima lebih dari 2 input! Menarik
Luis Mendo
@LuisMendo Yup 2+
Suever
3

MATLAB, 49 byte

@(x)find(~any(bsxfun(@rem,1:prod(1:x),(1:x)')),1)
Suever
sumber
+1 untukbsxfun
flawr
3

Perl 6 , 13 byte

{[lcm] 1..$_}

Blok kode anonim yang menciptakan Rentang dari 1 hingga input (inklusif), dan kemudian menguranginya dengan &infix:<lcm>.

Contoh:

#! /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
sumber
ideone.com/gR4SK5
Brad Gilbert b2gills
2

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

Terima kasih @ConorOBrien dan @Neil

y=>(g=(a,b)=>b?g(b,a%b):a,[...Array(y)].map((_,i)=>y=y*++i/g(y,i)),y)
Bulu ayam
sumber
b?g(b,a%b):amenghemat satu byte.
Neil
y*++i/g(y,i)menyimpan beberapa byte lagi.
Neil
1

05AB1E, 20 byte

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

Penjelasan

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

Cobalah online

Emigna
sumber
1

Minkolang 0,15 , 12 byte

Saya memiliki dua solusi 12-byte, dan telah memasukkan keduanya.

1n[i1+4$M]N.

Coba di sini!

Penjelasan

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.

Tentang semudah yang didapat.


11nLd[4$M]N.

Coba di sini!

Penjelasan

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.

Solusi ketiga dapat diturunkan dari ini: hapus a 1dan tambahkan dsetelah saat ini d. Dalam kedua kasus, angka tambahan diperlukan karena loop for berjalan satu kali terlalu banyak, dan membuatnya berjalan satu kali lebih sedikit membutuhkan dua byte ( 1-tepat sebelum [).

El'endia Starman
sumber
1

Ruby, 25 byte

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

Ruby, 25 byte

g=->n{n<1?1:a[n-1].lcm n}
Peter Kagey
sumber
1
Halo, dan selamat datang di PPCG! Pos pertama yang bagus! Anda tidak harus memberi nama fungsi Anda, sehingga Anda dapat menghapus g=.
NoOneIsHere
Fungsi anonim diizinkan.
Erik the Outgolfer
1

Bahasa GameMaker, 60 byte

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

Berdasarkan logika jawaban anatolyg.

Timtech
sumber
1

PHP, 61 52 48 byte

disimpan 9 byte berkat @ user59178, 4 byte dengan menggabungkan loop.

Rekursi dalam PHP besar karena functionkata kunci; jadi saya menggunakan iterasi.
Dan dengan beberapa trik "kecil", saya sekarang bahkan mengalahkan JS Arnauld .

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

mengambil input dari argumen baris perintah. Jalankan dengan -r.

kerusakan

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

Itu sebenarnya dua loop dalam satu:

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

Catatan: disalin dari jawaban saya pada duplikat

Titus
sumber
1

Japt, 10 byte

Tidak ada LCM bawaan.

@õ e!vX}a1

Cobalah

Shaggy
sumber
0

Pyke, 3 byte, tidak bersaing

S.L

Coba di sini!

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

Hoon , 67 byte

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

Buat daftar [1..n], lipat daftar dengan lcm. Sayangnya, stdlib Hoon tidak memiliki pre-built yang dapat saya gunakan: /

Pengaturan rendering
sumber
0

𝔼𝕊𝕄𝕚𝕟, 7 karakter / 9 byte

Мū…⩤⁽1ï

Try it here (ES6 only).

Hanya satu kisaran inklusif LCM dari 1 hingga input.

Mama Fun Roll
sumber
0

AWK, 42 byte

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

Penggunaan baris perintah:

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

Saya tidak melihat AWKsolusi dan duplikat dari pertanyaan yang baru saja diposting kemarin, jadi saya pikir saya akan menggabungkan ini. Ini pemecahan yang agak lambat 19atau lebih besar pada kotak saya, tetapi berhasil.

Robert Benson
sumber
0

QBIC , 35 32 byte

Ini membawaku ke sini.

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

Penjelasan:

:        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]

Berikut adalah versi yang berhenti menguji qketika btidak membaginya dengan bersih. Juga, urutan pengujian bmelawan qdibalik dalam asumsi bahwa tinggi b's akan lebih sulit untuk bagi dengan (take 2, 3, 4misalnya: jika %2=0, %4bisa !0. Begitu juga sebaliknya tidak begitu banyak ...).

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

8 , 23 byte

Kode

1 ' lcm rot 2 swap loop

Kode ini menghasilkan pseudofactorial pada TOS

Penggunaan dan contoh

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

Atau lebih jelas

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

ok> 7 pseudofact .
420
Kekacauan Manor
sumber