Tentukan Superabundance

21

Angka superabundan adalah bilangan bulat n yang menetapkan batas atas baru untuk rasio dengan fungsi jumlah pembagi σ. Dengan kata lain, n adalah superabundant jika dan hanya jika, untuk semua bilangan bulat positif x yang kurang dari n :

σ(n)n>σ(x)x

Untuk beberapa nilai:

n   σ(n)   σ(n)/n   superabundant
1   1      1.0000   yes
2   3      1.5000   yes
3   4      1.3333   no
4   7      1.7500   yes
5   6      1.2000   no
6   12     2.0000   yes
7   8      1.1429   no
8   15     1.8750   no
9   13     1.4444   no

Daftar yang lebih panjang (untuk kasus uji) dapat ditemukan di OEIS A004394 .

Satu test case negatif yang sangat direkomendasikan (jika juru bahasa Anda dapat mengatasinya) adalah 360360, karena itu terkait dengan angka superundundan terakhir.

Tantangan

Program Anda harus mengambil dalam bilangan bulat positif tunggal, dan menampilkan nilai true atau falsey yang mewakili apakah bilangan bulat itu superundung.

Karena ini adalah , jawaban terpendek dalam byte akan menang.

Nissa
sumber

Jawaban:

7

Jelly , 7 byte

Æs÷$ÞṪ=

Cobalah online!

Jelly , 8 byte

Æs÷$ÐṀ⁼W

Cobalah online!

Test Suite!

Penjelasan

÷s ÷ $ ÐṀ⁼W ~ Program lengkap (monadik).

    ÐṀ ~ Menjaga elemen dengan nilai tautan maksimal (rentang otomatis).
~s ~ Jumlah pembagi.
  ÷ $ ~ Membagi dengan elemen saat ini.
      ⁼W ~ Periksa kesetaraan dengan input yang dibungkus dengan singleton.
         ~ (untuk bilangan bulat seperti 360360)
Tuan Xcoder
sumber
Saya pikir Anda bisa melakukannya Æs÷$ÐṀ=selama 7 byte. Saya tidak menyadari ÐṀrangified, itu berguna untuk diketahui.
dylnan
@dylnan Tidak, saya tidak bisa. Meskipun tidak dapat diuji online, gagal untuk 360360. Sebenarnya, ini adalah versi awal saya
Tn. Xcoder
Mengapa itu gagal 360360?
dylnan
@ Dylnan 360360adalah angka pertama yang gagal untuk (saya pikir), karena ini adalah angka pertama yang mengikat hasil yang terjadi sebelumnya. (dan hasilnya adalah [0, 1])
Tn. Xcoder
@ Mr.Xcoder saya mengerti, terima kasih
dylnan
5

Haskell , 73 byte

-1 byte terima kasih kepada Tn. Xcoder. -7 byte terima kasih kepada Laikoni.

r=read.show
s n=sum[r i|i<-[1..n],n`mod`i<1]/r n
f n=all((s n>=).s)[1..n]

Cobalah online!

Sistem tipe Haskell tidak terlalu golf ...

benar-benar manusiawi
sumber
5

Haskell , 64 63 61 byte

-1 byte terima kasih kepada Tn . Xcoder .

-2 byte terima kasih kepada Lynn .

a!x=a*sum[y|y<-[1..x],mod x y<1]
f n=and[x!n>n!x|x<-[1..n-1]]

Cobalah online!

pengguna28667
sumber
4

Oktaf , 41 byte

@(n)([~,p]=max((x=1:n)*~mod(x,x')./x))==n

Cobalah online!

Penjelasan

@(n)                                       % Define anonymous function of n
                x=1:n                      % Range from 1 to n. Call that x
                        mod(x,x')          % n×n matrix of all pair-wise moduli
                       ~                   % Logical negate. True means it's a divisor
               (     )*                    % Matrix-multiply x times the above matrix
                                           % (gives the dot product of vector x times
                                           % each column of the matrix)
                                 ./x       % Divide each column by each entry in x
     [~,p]=max(                     )      % Index of first occurrence of maximum
    (                                )==n  % Does it equal n?
Luis Mendo
sumber
3

J , 35 byte

Terima kasih kepada Mr.Xcoder untuk menemukan masalah dan untuk memperbaiki masalah ini!

[:([:*/{:>}:)@(%~>:@#.~/.~&.q:)1+i.

Cobalah online!

Galen Ivanov
sumber
1
Gagal untuk 360360(lihat tantangan untuk detail lebih lanjut: Satu test case negatif yang sangat direkomendasikan adalah 360360, karena itu terkait dengan angka superundundan terakhir. ).
Tn. Xcoder
1
Diperbaiki +3 byte. Cobalah online . Bekerja pada golf. Saya suka menggunakan #.~banyak (jujur ​​seluruh fungsi jumlah pembagi sangat bagus). Apa yang salah, adalah, meskipun pemikiran melakukan {:=>./itu cerdas, itu tidak memuaskan bagian "lebih besar dari" dari pertanyaan itu.
cole
1
Inilah yang saya datang dengan untuk menggantikan fungsi sigma, yang pada panjang yang sama saat: (1#.{:(]*0=|~)])\ . Ada yang salah dengan itu, mungkin Anda memiliki beberapa pemikiran?
cole
1
@cole Kredit untuk jumlah fungsi pembagi pergi ke Roger Hui, dalam esai ini . Saya juga mulai menulis fungsi sigma lain tetapi berhenti setelah saya mencapai 9 byte dan memutuskan itu tidak akan lebih pendek dari yang dengan faktorisasi prima. Terima kasih telah memperbaiki masalah!
Galen Ivanov
@cole Kata kerja terpendek lainnya untuk jumlah pembagi yang saya buat adalah ini: (1#.]*0=|~)1+i.Ini adalah pengait dan tidak pas dengan mudah ke tempatnya :)
Galen Ivanov
3

Julia 0,6 , 52 byte

n->indmax(sum(x for x=1:m if m%x<1)//m for m=1:n)==n

Cobalah online!

Solusi ini menggunakan bilangan rasional untuk memastikan kebenaran dalam hal kesetaraan. (Pengujian 360360 membutuhkan waktu hampir 10 menit.)

Menggunakan floating point, 2 byte dapat disimpan dengan pembagian kiri:

n->indmax(m\sum(x for x=1:m if m%x<1)for m=1:n)==n
LukeS
sumber
3

Pyth , 14 byte

( FryAmTheEggman menyimpan 1 byte)

qh.Mcs*M{yPZZS

Coba di sini! atau lihat lebih banyak test case.

Hanya pengajuan Pyth wajib saya yang kemungkinan besar golf.

Bagaimana?

qh.Mcs * M {yPZZS ~ Program lengkap. Q = input.

             S ~ Bilangan bulat dalam kisaran [1, Q].
  .M ~ Dapatkan elemen dengan nilai fungsi maksimal.
    cs * M {yPZZ ~ Fungsi kunci: menggunakan variabel Z.
         yPZ ~ Powerset dari faktor utama Z.
        {~ Deduplicated.
      * M ~ Produk masing-masing.
     s ~ Dan dijumlahkan.
    c Z ~ Dibagi oleh Z.
 h ~ Elemen pertama.
q ~ Periksa kesetaraan dengan input. Outputs Benar atau Salah.
Tuan Xcoder
sumber
3

05AB1E , 10 byte

LÑOā/ZQ¨_P

Cobalah online! atau sebagai Test suite

Penjelasan

L            # push range [1 ... input]
 Ñ           # divisors of each
  O          # sum of each
   ā/        # divide each by its 1-based index
     Z       # get max
      Q      # compare to each
       ¨     # remove the last element
        _    # logical negation
         P   # product
Emigna
sumber
Saya pikir (walaupun saya tidak yakin) ini gagal untuk 360360(lihat tantangan untuk lebih jelasnya: Satu test case negatif yang sangat direkomendasikan adalah 360360, karena ini terkait dengan angka superabundan terakhir. ).
Tn. Xcoder
@ Mr.Xcoder: Benar. Memperbaikinya, tetapi mungkin ada cara yang lebih baik untuk melakukan ini sekarang.
Emigna
3

Python 3 , 77 byte

-1 byte terima kasih kepada Rod. -3 byte terima kasih kepada Dennis.

lambda n:max(range(1,n+1),key=lambda k:sum((k%i<1)/i for i in range(1,k)))==n

Cobalah online!

benar-benar manusiawi
sumber
2

R menggunakan numbers, 59 byte

f=function(n)which.max(sapply(1:n,numbers::Sigma)/(1:n))==n
Joseph Wood
sumber
2

Mathematica, 53 50 byte

a=Tr@Divisors@#/#&;AllTrue[a@#-Array[a,#-1],#>0&]&

Fungsi murni. Mengambil bilangan bulat sebagai input dan mengembalikan Trueatau Falsesebagai output.

LegionMammal978
sumber
Apakah sesuatu seperti Tr@Divisors@#bekerja?
user202729
1

Japt v2.0a0, 12 16 byte

Otak yang kurang tidur sepertinya tidak bisa memperbaiki ini lebih jauh!

Pengembalian 1untuk kebenaran atau 0untuk kepalsuan.

Æâ x÷U >Xâ x÷XÃ×

Cobalah

Mengorbankan 4 byte untuk ditangani 360360.


Penjelasan

  • Input bilangan bulat implisit U.
  • Æ Ãmembuat array bilangan bulat dari 0ke U-1dan melewati masing-masing melalui fungsi berikut sebagai X.
  • âmendapat pembagi dari U.
  • ÷Umembagi masing-masing dengan U.
  • x jumlah hasilnya.
  • mendapat pembagi dari X.
  • ÷Xmembagi masing-masing dengan X.
  • x jumlah hasilnya.
  • > memeriksa apakah hasil pertama lebih besar dari yang kedua.
  • × mengurangi array boolean yang dihasilkan oleh perkalian.
Shaggy
sumber
1
Jika pendekatan Anda saat ini cocok dengan penjelasan Anda, itu gagal untuk 360360atau bilangan bulat lainnya: Satu test case negatif yang sangat direkomendasikan (jika penerjemah Anda dapat mengatasinya) adalah 360360, karena itu terkait dengan nomor
superabundan
@ Mr.XCoder: Kacang, Anda benar! Itu mungkin akan dikenakan biaya beberapa byte ketika saya punya waktu untuk memperbaikinya.
Shaggy
@ Mr.Xcoder: Diperbaiki untuk saat ini, harus kembali lagi nanti untuk melihat apakah saya dapat memperbaikinya.
Shaggy
0

APL + WIN, 37 byte

 ↑1=⍒⌽(+/¨((0=(⍳¨n)|¨n)×⍳¨n)~¨⊂0)÷n←⍳⎕

Meminta input layar.

Graham
sumber
0

C (gcc), 99 byte

s(n,j,k){for(j=k=0;j++<n;)k+=n%j?0:j;n=k;}f(n,i,r){for(i=r=0;++i<n;)r=1.*s(n)/n<1.*s(i)/i?:r;r=!r;}

Cobalah online!

C, 108 byte

float s(n,j,k){for(j=k=0;j++<n;)k+=n%j?0:j;return k;}f(n,i,r){for(i=r=0;++i<n;)s(n)/n<s(i)/i&&++r;return!r;}

Cobalah online!

Steadybox
sumber
Jadi, mengapa sperlu mengembalikan pelampung?
Nissa
@StephenLeppik Untuk divisi penggunaan pelampung bukan integer divisi ketika membandingkan s(n)/nke s(i)/i.
Steadybox
0

Cepat , 120 118 byte

let s={n in Float((1...n).reduce(0){n%$1>0 ?$0:$0+$1})}
{n in(1..<n).reduce(0){max($0,s($1)/Float($1))}<s(n)/Float(n)}

Butuh beberapa waktu (sekitar 6 detik pada TIO) untuk dikompilasi karena deklarasi tipe implisit di Swift.

Cobalah online!

Herman L.
sumber
0

Funky , 79 byte

d=n=>fors=i=0i<=n i++s+=i*!n%i
f=n=>{forc=1c<n c++if(d(n)/n)<=d(c)/c return0 1}

Dijelaskan

Ini pertama mendefinisikan fungsi dyang merupakan σfungsi, dan ini adalah versi golf

function d(n){
    var s = 0;
    for(var i=0; i<n; i++){
        if(n%i == 0){
            s += i;
        }
    }
    return s;
}

Kita dapat mengatur i ke 0, karena i*n%0akan selalu sama 0*..., dengan demikian0 .

Bagian selanjutnya dari ini mendefinisikan fungsi f, yang merupakan fungsi Superabandunce, dan itu hanya bentuk golf

function f(n){
    for(var c=1; c<n; c++){
        if( (d(n)/n) <= (d(c)/c) ){
            return 0;
        }
    }
    return 1;
}

Dan ini hanya memeriksa, seperti yang disarankan oleh tantangan, bahwa semua bilangan bulat dari 1 hingga n-1 memiliki d(n)/nkurang dari input.

Cobalah online!

ATaco
sumber
0

APL (Dyalog) , 33 byte

{⍵=⊃⌽+⌿∘.≤⍨((+/⍳(/⍨)0=⍳|⊢)÷⊢)¨⍳⍵}

Cobalah online!

Uriel
sumber
0

Sekam , 9 byte

εü<m§ṁ/Ḋṫ

Cobalah online! Terlalu lambat untuk test case 360360.

Penjelasan

εü<m§ṁ/Ḋṫ  Implicit input, say n=6.
        ṫ  Decreasing range: [6,5,4,3,2,1]
   m       Map this function (example argument k=4):
       Ḋ    Divisors of k: [1,2,4]
    §ṁ      Map and sum
      /     division by k: 7/4
           Result: [2,6/5,7/4,4/3,3/2,1]
 ü         Remove duplicates by
  <        strict comparison. This greedily extracts a non-decreasing subsequence: [2]
ε          Is it a singleton list? Yes.
Zgarb
sumber
Saya punya £ü¤<§ṁ/ḊN. Menciptakan seluruh daftar nomor yang sangat banyak
H.PWiz
0

Perl 5, 84 byte

say!grep$a[-1]<=$a[$_],0..(@a=map{$i=$_;my$j;map{$i%$_ or$j+=$_/$i}1..$i;$j}1..<>)-2

membutuhkan -E(gratis)

implementasi langsung dari spesifikasi, golf

msh210
sumber
0

APL (NARS), 61 karakter, 122 byte

r←f w;m;k
r←m←0
r+←1⋄k←r÷⍨11πr⋄→3×⍳r≥w⋄→2×⍳∼m<k⋄m←k⋄→2
r←k>m

11π adalah jumlah fungsi faktor

  (⍳9),¨ f¨1..9
1 1  2 1  3 0  4 1  5 0  6 1  7 0  8 0  9 0 
  f 360360
0
RosLuP
sumber