Anzahl der Faktorsummen

12

Bei einer positiven ganzen Zahl n> 1 bestimmen Sie, wie viele Zahlen gebildet werden können, indem Sie ganze Zahlen größer als 1 addieren, deren Produkt n ist . Wenn beispielsweise n = 24 ist , können wir n wie folgt als Produkt ausdrücken

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

Wir können auf diese Weise die folgenden Zahlen erhalten:

24, 14, 11, 10, 9

Das sind insgesamt 5 Zahlen, also ist unser Ergebnis 5.

Aufgabe

Schreiben Sie ein Programm oder eine Funktion, die n als Eingabe verwendet und die Anzahl der Ergebnisse zurückgibt, die auf diese Weise erhalten werden können.

Dies ist eine Frage, daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.

OEIS-Sequenz

OEIS A069016

Post Rock Garf Hunter
quelle
1
Vorgeschlagener Testfall 240
Jonathan Allan
Da 36 viele Debatten ausgelöst hat, empfehle ich dies als Testfall.
Kritixi Lithos
3
@ WheatWizard 12 * 3
Business Cat
1
Ich habe 2,2,3,3 -> 10, 2,6,3 -> 11, 2,2,9 -> 13, 12,3 -> 15, 2,18 -> 20,36 -> 36
Business -
2
36 sollte 7 sein, weil (2*3)+(2*3)=12auch in der Liste sein sollte.
Jonathan Allan

Antworten:

6

Brachylog , 8 Bytes

{~×≜+}ᶜ¹

Probieren Sie es online!

Erläuterung

{    }ᶜ¹  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.

Ich bin mir nicht ganz sicher, warum nur Listen mit Elementen über 1 erstellt werden, aber es scheint so zu sein, was bei dieser Herausforderung großartig funktioniert.

Zgarb
quelle
Es werden nur Listen mit Elementen über 1 erstellt, da es sonst unendlich viele Listen gibt, was bei solchen Herausforderungen oftmals schlecht ist.
Fatalize
4

Gaia , 9 14 13 Bytes

Fehler behoben auf Kosten von 5 Bytes dank Jonathan Allan, dann 1 Byte Golf.

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

Probieren Sie es online!oder versuche es als Testsuite

Erläuterung

ḍ              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
Geschäfts-Katze
quelle
Können Sie einen TIO-Link bereitstellen, der die entsprechenden Ausgänge mit den Nummern 1 bis einschließlich 36 enthält?
Kritixi Lithos
Dies ist genau wie die Gelee-Antwort ...
Erik der Outgolfer
1
Das OP sagt, die Ausgabe für 36 sollte 5 sein, nicht 6
Kritixi Lithos
1
Laut OEIS gibt 36 7 statt 5, aber Ihre gibt 6
Kritixi Lithos
1
Anscheinend lässt Gaia aus[6 6]
Kritixi Lithos
2

Jelly ,  11 15  14 Bytes

+4 Bytes zur Behebung eines Fehlers (vielleicht ein besserer Weg?)
-1 Byte durch Missbrauch der Symmetrie

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

Eine monadische Verknüpfung, die positive ganze Zahlen aufnimmt und zurückgibt

Probieren Sie es online! oder sehen Sie sich eine Testsuite an

Wie?

Aktualisierung...

Æ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
quelle
1

Python 2 , 206 Bytes

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

Probieren Sie es online!

Erläuterung

    # 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
quelle
1
194 Bytes
OVS
1

Mathematica, 110 Bytes

If[#==1,1,Length@Union[Tr/@Select[Array[f~Tuples~{#}&,Length[f=Rest@Divisors[s=#]]]~Flatten~1,Times@@#==s&]]]&
J42161217
quelle
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)

Ungolfed:

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
)

Testfälle:

Um zu überprüfen, ob die Funktion die richtigen Summen berechnet, können wir die Schlüssel des Objekts ausgeben, anstatt 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
quelle
1

Python 3 , 251 Bytes

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

Probieren Sie es online!

Das Design ist grundlegend:

  1. zerlegen Sie n in seine Primfaktoren (ein Primfaktor kann mehrmals vorkommen:) 16 -> [2,2,2,2]. Das ist die Funktion f.

  2. Berechnen Sie die Partitionen der Liste der Primfaktoren und multiplizieren Sie die Faktoren in jeder Partition. Die Partitionen befinden sich unter /programming//a/30134039 , und die Produkte werden im laufenden Betrieb berechnet. Das ist die Funktiont .

  3. Die letzte Funktion erhält die Produkte jeder Partition von n und summiert sie, um die Anzahl der verschiedenen Werte zu erhalten.

Das Ergebnis für 2310=2*3*5*7*11ist 49.

EDIT : Vielleicht muss behoben werden, aber ich habe keine Zeit, es jetzt anzusehen (ich habe es eilig). Hinweis: Stimmt das Ergebnis 2310=2*3*5*7*11? Das glaube ich nicht.

EDIT2 : Riesige Verlegenheit. Siehe oben. Vorherige (Buggy-) Version war: Online ausprobieren!

fberechnet die Faktoren (, mit einem (0, n)statt (1, n)als erstes Element.

Das Lambda teilt jeden Faktor in "Subfaktoren" und summiert diese "Subfaktoren".

jferard
quelle
1
-19 Bytes.
Notjagan
Vielen Dank an @notjagan, aber der ursprüngliche Code war so falsch ...
jferard
Danke an @HalvardHummel, aber die gleiche Bemerkung wie oben.
Jferard