Jumlah jumlah faktor

12

Diberikan bilangan bulat positif n> 1 menentukan berapa angka yang dapat dibuat dengan menambahkan bilangan bulat lebih besar dari 1 yang produknya adalah n . Sebagai contoh jika n = 24 kita dapat mengekspresikan n sebagai produk dengan cara berikut

24 = 24             -> 24            = 24
24 = 12 * 2         -> 12 + 2        = 14
24 = 6 * 2 * 2      -> 6 + 2 + 2     = 10
24 = 6 * 4          -> 6 + 4         = 10
24 = 3 * 2 * 2 * 2  -> 3 + 2 + 2 + 2 = 9
24 = 3 * 4 * 2      -> 3 + 4 + 2     = 9
24 = 3 * 8          -> 3 + 8         = 11

Kita bisa mendapatkan angka-angka berikut dengan cara ini:

24, 14, 11, 10, 9

Itu adalah total 5 angka, jadi hasil kami adalah 5.

Tugas

Tulis program atau fungsi yang mengambil n sebagai input dan mengembalikan jumlah hasil yang dapat diperoleh dengan cara ini.

Ini adalah pertanyaan sehingga jawaban akan dinilai dalam byte, dengan lebih sedikit byte yang lebih baik.

Urutan OEIS

OEIS A069016

Ad Hoc Garf Hunter
sumber
1
Kasing uji yang disarankan 240
Jonathan Allan
Karena 36 telah menyebabkan banyak perdebatan, saya sarankan itu sebagai ujian.
user41805
3
@WheatWizard 12 * 3
Bisnis Cat
1
Saya memiliki 2,2,3,3 -> 10, 2,6,3 -> 11, 2,2,9 -> 13, 12,3 -> 15, 2,18 -> 20,36 -> 36
Bisnis Cat
2
36 harus 7 karena (2*3)+(2*3)=12harus ada dalam daftar juga.
Jonathan Allan

Jawaban:

6

Brachylog , 8 byte

{~×≜+}ᶜ¹

Cobalah online!

Penjelasan

{    }ᶜ¹  Count unique results of this predicate:
 ~×       Create list of numbers whose product is the input.
   ≜      Label the list, forcing it to take a concrete value.
    +     Take its sum.

Saya tidak sepenuhnya yakin mengapa hanya menghasilkan daftar dengan elemen di atas 1, tetapi tampaknya melakukannya, yang bekerja sangat baik dalam tantangan ini.

Zgarb
sumber
Ini hanya menghasilkan daftar dengan elemen di atas 1 karena jika tidak ada banyak daftar yang tak terbatas, yang sering kali buruk dalam tantangan seperti ini.
Fatalkan
4

Gaia , 9 14 13 byte

Bug diperbaiki dengan biaya 5 byte berkat Jonathan Allan, kemudian 1 byte di-golf.

ḍfḍ¦e¦Π¦¦Σ¦ul

Cobalah online! atau coba sebagai test suite

Penjelasan

ḍ              Prime factors
 f             Permutations
  ḍ¦           Get the partitions of each permutation
    e¦         Dump each list of partitions (1-level flatten the list)
      Π¦¦      Product of each partition
         Σ¦    Sum each group of products
           u   Deduplicate
            l  Length
Kucing Bisnis
sumber
Bisakah Anda memberikan tautan TIO yang berisi keluaran yang sesuai angka 1 hingga 36 inklusif?
user41805
Ini persis seperti jawaban Jelly ...
Erik the Outgolfer
1
OP mengatakan output untuk 36 harus 5, bukan 6
user41805
1
Menurut OEIS, 36 memberi 7 bukannya 5, tetapi Anda memberi 6
user41805
1
Rupanya Gaia keluar[6 6]
user41805
2

Jelly ,  11 15  14 byte

+4 byte memperbaiki bug (mungkin cara yang lebih baik?)
-1 byte dengan menyalahgunakan simetri

ÆfŒ!ŒṖ€ẎP€S€QL

Tautan monadik yang mengambil dan mengembalikan bilangan bulat positif

Cobalah online! atau lihat test suite

Bagaimana?

Memperbarui ...

ÆfŒ!ŒṖ€ẎP€S€QL - Link: number, n      e.g. 30
Æf             - prime factors of n        [2,3,5]
  Œ!           - all permutations          [[2,3,5],[2,5,3],[3,2,5],[3,5,2],[5,2,3],[5,3,2]]
    ŒṖ€        - all partitions for €ach   [[[[2],[3],[5]],[[2],[3,5]],[[2,3],[5]],[[2,3,5]]],[[[2],[5],[3]],[[2],[5,3]],[[2,5],[3]],[[2,5,3]]],[[[3],[2],[5]],[[3],[2,5]],[[3,2],[5]],[[3,2,5]]],[[[3],[5],[2]],[[3],[5,2]],[[3,5],[2]],[[3,5,2]]],[[[5],[2],[3]],[[5],[2,3]],[[5,2],[3]],[[5,2,3]]],[[[5],[3],[2]],[[5],[3,2]],[[5,3],[2]],[[5,3,2]]]]
       Ẏ       - tighten                   [[[2],[3],[5]],[[2],[3,5]],[[2,3],[5]],[[2,3,5]],[[2],[5],[3]],[[2],[5,3]],[[2,5],[3]],[[2,5,3]],[[3],[2],[5]],[[3],[2,5]],[[3,2],[5]],[[3,2,5]],[[3],[5],[2]],[[3],[5,2]],[[3,5],[2]],[[3,5,2]],[[5],[2],[3]],[[5],[2,3]],[[5,2],[3]],[[5,2,3]],[[5],[3],[2]],[[5],[3,2]],[[5,3],[2]],[[5,3,2]]]
        P€     - product for €ach          [[30],[6,5],[10,3],[2,3,5],[30],[10,3],[6,5],[2,5,3],[30],[6,5],[15,2],[3,2,5],[30],[15,2],[6,5],[3,5,2],[30],[10,3],[15,2],[5,2,3],[30],[15,2],[10,3],[5,3,2]]
               -   ...this abuses the symmetry saving a byte over P€€
          S€   - sum €ach                  [30,11,13,10,30,13,11,10,30,11,17,10,30,17,11,10,30,13,17,10,30,17,13,10][10,17,11,30,10,17,13,30,10,13,11,30,10,13,17,30,10,11,13,30,10,11,17,30]
            Q  - de-duplicate              [30,11,13,10,17]
             L - length                    5
Jonathan Allan
sumber
1

Python 2 , 206 byte

k=lambda n,i=2:n/i*[k]and[k(n,i+1),[i]+k(n/i)][n%i<1]
def l(t):
 r=[sum(t)]
 for i,a in enumerate(t):
    for j in range(i+1,len(t)):r+=l(t[:i]+[a*t[j]]+t[i+1:j]+t[j+1:])
 return r
u=lambda n:len(set(l(k(n))))

Cobalah online!

Penjelasan

    # Finds the prime factors
k=lambda n,i=2:n/i*[k]and[k(n,i+1),[i]+k(n/i)][n%i<1]
    # Function for finding all possible numbers with some repetition
def l(t):
    # Add the current sum
 r=[sum(t)]
    # For each number in the current factors
 for i,a in enumerate(t):
    # For all numbers further back in the current factors, find all possible numbers when we multiply together two of the factors
    for j in range(i+1,len(t)):r+=l(t[:i]+[a*t[j]]+t[i+1:j]+t[j+1:])
 return r
    # Length of set for distinct elements
u=lambda n:len(set(l(k(n))))
Halvard Hummel
sumber
1
194 byte
ovs
1

Mathematica, 110 byte

If[#==1,1,Length@Union[Tr/@Select[Array[f~Tuples~{#}&,Length[f=Rest@Divisors[s=#]]]~Flatten~1,Times@@#==s&]]]&
J42161217
sumber
1

JavaScript (ES6) 107 byte

f=(n,o,s=0,i=2,q=n/i)=>(o||(o={},o[n]=t=1),i<n?(q>(q|0)|o[e=s+i+q]||(o[e]=t+=1),f(q,o,s+i),f(n,o,s,i+1)):t)

Tidak Disatukan:

f=(n,                                 //input
   o,                                 //object to hold sums
   s=0,                               //sum accumulator
   i=2,                               //start with 2
   q=n/i                              //quotient
  )=>(
  o||(o={},o[n]=t=1),                 //if first call to function, initialize o[n]
                                      //t holds the number of unique sums
  i<n?(                               //we divide n by all numbers between 2 and n-1
    q>(q|0)|o[e=s+i+q]||(o[e]=t+=1),  //if q is integer and o[s+i+q] is uninitialized,
                                      //... make o[s+i+q] truthy and increment t
    f(q,o,s+i),                       //recurse using q and s+i
    f(n,o,s,i+1)                      //recurse using n with the next i
  ):t                                 //return t
)

Kasus uji:

Untuk memverifikasi bahwa fungsi menghitung jumlah yang benar, kami dapat menampilkan kunci objek alih-alih t:

f=(n,o,s=0,i=2,q=n/i)=>(o||(o={},o[n]=t=1),i<n?(q>(q|0)|o[e=s+i+q]||(o[e]=t+=1),f(q,o,s+i),f(n,o,s,i+1)):Object.keys(o))

console.log(f(24));  //9, 10, 11, 14, 24

Rick Hitchcock
sumber
1

Python 3 , 251 byte

lambda n:1 if n==1else len(set(sum(z)for z in t(f(n))))
f=lambda n:[]if n==1else[[i]+f(n//i)for i in range(2,n+1)if n%i==0][0]
t=lambda l:[l] if len(l)==1else[[l[0]]+r for r in t(l[1:])]+[r[:i]+[l[0]*e]+r[i+1:]for r in t(l[1:])for i,e in enumerate(r)]

Cobalah online!

Desainnya dasar:

  1. faktorisasi n menjadi faktor prima (faktor prima dapat muncul beberapa kali 16 -> [2,2,2,2]:). Itulah fungsinya f.

  2. hitung partisi dari daftar faktor prima, dan gandakan faktor di setiap partisi. Partisi ditemukan seperti di /programming//a/30134039 , dan produk dihitung dengan cepat. Itulah fungsinya t.

  3. Fungsi terakhir mendapatkan produk dari setiap partisi n dan menjumlahkannya, mendapatkan jumlah nilai yang berbeda.

Hasilnya 2310=2*3*5*7*11adalah 49.

EDIT : Mungkin perlu diperbaiki, tapi saya tidak punya waktu untuk melihatnya sekarang (saya sedang terburu-buru). Petunjuk: apakah hasilnya benar 2310=2*3*5*7*11? Saya rasa tidak.

EDIT2 : Perbaikan besar. Lihat di atas. Versi sebelumnya (buggy) adalah: Coba online!

fmenghitung faktor (, dengan (0, n)bukan (1, n)sebagai elemen pertama.

Lambda membagi masing-masing faktor menjadi "sub-faktor" dan menjumlahkan "sub-faktor" tersebut.

jferard
sumber
1
-19 byte.
notjagan
Terima kasih kepada @notjagan, tetapi kode awalnya sangat salah ...
jferard
Terima kasih kepada @HalvardHummel, tetapi komentar yang sama seperti di atas.
jferard