Sehr zusammengesetzte Zahlen

23

Eine stark zusammengesetzte Zahl ist eine positive Ganzzahl mit mehr Teilern als jede kleinere positive Ganzzahl. Dies ist die OEIS-Sequenz A002182 . Seine ersten 20 Amtszeiten sind

1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560

Zum Beispiel 4ist in der Sequenz, weil es 3 Teiler hat (nämlich 1, 2, 4), während 3 nur 2 Teiler hat, 2 auch 2 Teiler hat und 1 1 Teiler hat.

Herausforderung

Bei einer positiven Ganzzahleingabe n geben Sie nach Ihrer Wahl entweder die n- te zusammengesetzte Zahl oder die ersten n zusammengesetzten Zahlen aus (die Auswahl muss jedoch für jede Eingabe n gleich sein ).

Regeln

Das Programm oder die Funktion sollte theoretisch für beliebig große Eingaben bei unbegrenzter Zeit und unbegrenztem Arbeitsspeicher und ohne Berücksichtigung von Datentypbeschränkungen funktionieren. Im Wesentlichen bedeutet dies, dass eine endliche Anzahl von Werten nicht hartcodiert werden muss.

In der Praxis sollte das Programm oder die Funktion in einer angemessenen Zeitspanne, beispielsweise weniger als 1 Minute, für n bis 20 ausgeführt werden. Die maximale Eingabe oder Ausgabe kann durch den Standarddatentyp Ihrer Sprache begrenzt sein (der Algorithmus sollte jedoch theoretisch funktionieren für beliebig große Zahlen).

Jedes sinnvolle Eingabe- und Ausgabeformat ist zulässig, auch unary.

Code Golf. Wenigste Bytes gewinnt.

Luis Mendo
quelle
Diese Unterhaltung wurde in den Chat verschoben .
Dennis
Kann der n- te Index null-indiziert sein oder muss dieser 1-indiziert sein?
Adnan
@AundN Daran hatte ich noch nicht gedacht, also nehmen wir an, dass beide akzeptiert werden. (Ich erinnere mich an einen Meta-Post, in dem sowohl 1-basiert als auch 0-basiert vorgeschlagen wird, aber ich kann ihn nicht finden. Jemand?)
Luis Mendo

Antworten:

4

05AB1E , 15 14 Bytes

Die Eingabe ist nullindexiert. Das heißt, dass n = 0gibt 1, n = 1gibt 2, etc. Code:

$µ>DÑgD®›i©¼}\

Erläuterung:

$               # Pushes 1 and input
 µ              # Counting loop, executes until the counting variable is equal to input
  >             # Increment (n + 1)
   DÑ           # Duplicate and calculate all divisors
     gD         # Get the length of the array and duplicate
       ®        # Retrieve element, standardized to zero
        ›i  }   # If greater than, do...
          ©     #   Copy value into the register
           ¼    #   Increment on the counting variable
             \  # Pop the last element in the stack

Berechnet n = 19 , was 7560in ungefähr 10 Sekunden ergeben sollte.

Probieren Sie es online!

Verwendet CP-1252- Codierung.

Adnan
quelle
5

Gelee, 15 Bytes

,®ÆDL€ṛ©0>/?µƓ#

Bei Eingabe von n werden die ersten n zusammengesetzten Zahlen ausgegeben.

Bei n = 20 dauert es weniger als zwei Sekunden. Online testen!

Wie es funktioniert

,®ÆDL€ṛ©0>/?µƓ#  Main link. No implicit input.

            µ    Push the chain to the left on the local link stack.
             Ɠ   Read an integer n from STDIN.
              #  Execute the chain for k = 0, 1, 2, ..., until it returned a truthy
                 value n times. Return the list of matches.

,®               Pair k with the value in the register (initially 0).
  ÆD             Compute the divisors of k and the register value.
    L€           Count both lists of divisors.
           ?     If
         >/        k has more divisors than the register value:
      ṛ©             Save k in the register and return k.
        0          Else: Return 0.

Alternative Version, 13 Bytes (nicht konkurrierend)

Während der unten stehende Code in der neuesten Version von Jelly, die dieser Herausforderung vorausgeht, funktioniert hat, war die Implementierung von Msehr langsam und hat das Zeitlimit nicht eingehalten. Dies wurde behoben.

ÆDL®;©MḢ’>µƓ#

Probieren Sie es online!

Wie es funktioniert

ÆDL®;©MḢ’>µƓ#  Main link. No implicit input.

          µ    Push the chain to the left on the local link stack.
           Ɠ   Read an integer n from STDIN.
            #  Execute the chain for k = 0, 1, 2, ..., until it returned a truthy
               value n times. Return the list of matches.

ÆD             Compute the divisors of k.
  L            Count them.
   ®;          Append the count to the list in the register (initially 0 / [0]).
     ©         Save the updated list in the register.
      M        Obtain all indices the correspond to maximal elements.
       Ḣ       Retrieve the first result.
        ’>     Subtract 1 and compare with k.
               This essentially checks if the first maximal index is k + 2, where
               the "plus 2" accounts for two leading zeroes (initial value of the
               register and result for k = 0).
Dennis
quelle
1
Es gibt auch RÆDL€MḢ=µƓ#(11 Bytes), aber es dauert 44 Minuten auf meinem Computer ...
Dennis
3

MATL , 26 24 Bytes

~XKx`K@@:\~s<?@5MXKx]NG<

Probieren Sie es online!

Die aktuell größte Anzahl der gefundenen Teiler befindet sich in der Zwischenablage K. Hochkompositzahlen (HCN) werden direkt auf dem Stapel abgelegt. In einer Schleife werden weiterhin Kandidaten für HCN getestet. Wenn eines gefunden wird, bleibt es auf dem Stapel und die Zwischenablage K wird aktualisiert. Die Schleife wird beendet, wenn die gewünschte Anzahl von HCN gefunden wurde.

~         % take input implicitly (gets stored in clipboard G). Transform into a 0 
          % by means of logical negation
XKx       % copy that 0 into clipboard K, and delete
`         % do...while
  K       %   push largest number of divisors found up to now
  @       %   push iteration index, i: current candidate to HCN
  @:      %   range [1,...,i]
  \       %   modulo operation
  ~s      %   number of zeros. This is the number of divisors of current candidate
  <       %   is it larger than previous largest number of divisors?
  ?       %   if so: a new HCN has been found
    @     %     push that number
    5M    %     push the number of divisors that was found
    XKx   %     update clipboard K, and delete
  ]       %   end if
  N       %   number of elements in stack
  G<      %   is it less than input? This the loop condition: exit when false
          % end do...while implicitly
          % display all numbers implicitly
Luis Mendo
quelle
3

Perl, 60 57 + 1 = 58 Bytes

$,++;$==grep$,%$_<1,1..$,;$_--,$m=$=if$=>$m;$_?redo:say$,

Benötigt -nund die freie -M5.010| -E:

$ perl -nE'$,++;$==grep$,%$_<1,1..$,;$_--,$m=$=if$=>$m;$_?redo:say$,' <<< 10 
120

Wie es funktioniert:

$,++;
     $==grep$,%$_<1,1..$,;                                # Calculate total numbers of divisors for `$,`
                          $_--,$m=$=if$=>$m;              # Set `$m`ax divisors to `$=`ivisors if `$m>$=`
                                            $_?redo:say$, # Repeat or print
undlrc
quelle
2

JavaScript (ES6) 72

Einfache Implementierung. Zeit nahe 20 Sekunden für Eingang 20

x=>{for(i=e=n=0;i<x;d>e&&(++i,e=d))for(d=1,j=++n;--j;)n%j||++d;return n}

Durch den Auswertungs-Trick könnte ein Byte eingespart werden, das die Laufzeit verdoppelt

x=>eval("for(i=e=n=0;i<x;d>e&&(++i,e=d))for(d=1,j=++n;--j;)n%j||++d;n")

Weniger golfen

x=>{
  for(i = e = 0, n = 1; i < x; n++)
  {
    for(d = 1, j = n; --j; )
    {
      if (n%j == 0) 
        ++d;
    }
    if (d > e)
      ++i,
      e = d;
  }
  return n;
}
edc65
quelle
2

Pyth, 17 16 Bytes

1 Byte danke an Jakube

uf<Fml{yPd,GTGQ1

Testsuite

Nimmt ein 0-indiziertes n und gibt die n-te zusammengesetzte Zahl zurück.

Erläuterung:

uf<Fml{yPd,GThGQ1
                     Input: Q = eval(input())
u              Q1    Apply the following function Q times, starting with 1.
                     Then output the result. lambda G.
 f           hG      Count up from G+1 until the following is truthy, lambda T.
          ,GT        Start with [G, T] (current highly comp., next number).
    m                Map over those two, lambda d.
        Pd           Take the prime factorization of d, with multiplicity.
       y             Take all subsets of those primes.
      {              Deduplicate. At this point, we have a list of lists of primes.
                     Each list is the prime factorization of a different factor.
     l               Take the length, the number of factors.
  <F                 Check whether the number of factors of the previous highly
                     composite number is smaller than that of the current number.
isaacg
quelle
1

Ruby, 70 69 67 66 64 62

->n{r=k=0
0until(r<t=(1..k+=1).count{|d|k%d<1})&&1>n-=t/r=t
k}

Einfache Implementierung.

Mitch Schwartz
quelle
1

C 98 Bytes

f,i,n,j;main(m){for(scanf("%d",&n);n--;printf("%d ",i))for(m=f;f<=m;)for(j=++i,f=0;j;)i%j--||f++;}

Versuch es hier aus .

Ungolfed

f,i,n,j;

main(m)
{
    for(scanf("%d",&n); /* Get input */
            n--; /* Loop while still HCN's to calculate... */
            printf("%d ",i)) /* Print out the last calculated HCN */
        for(m=f;f<=m;) /* Loop until an HCN is found... */
            for(j=++i,f=0;j;) /* Count the number of factors */
                i%j--||f++;
}
Cole Cameron
quelle
1

Python 3, 97 Bytes

i=p=q=0;n=int(input())
while q<n:
 c=j=0;i+=1
 while j<i:j+=1;c+=i%j==0
 if c>p:p=c;q+=1
print(i)

Ein vollständiges Programm, das Eingaben von STDIN entgegennimmt und die Ausgabe an STDOUT ausgibt. Dies gibt die nth 1-indexierte hoch zusammengesetzte Zahl zurück.

Wie es funktioniert

Dies ist eine einfache Implementierung. Die Eingabe nist der stark zusammengesetzte Zahlenindex.

Das Programm durchläuft die ganzen Zahlen i. Für jede ganze Zahl wird jkleiner als i, i mod jgenommen; Wenn dies der Fall ist 0, jmuss dies ein Faktor von sein, iund der Zähler cwird inkrementiert, wobei die Anzahl der Teiler inach der Schleifenbildung angegeben wird. pist die bisher höchste Anzahl von Teilern. Wenn also c > peine neue, stark zusammengesetzte Zahl gefunden wurde, wird der Zähler qinkrementiert. Einmal q = n, imuss dien th hoch zusammengesetzte Zahl, und diese gedruckt werden.

Probieren Sie es auf Ideone

(Dies dauert ca. 15 Sekunden n = 20und überschreitet damit das Zeitlimit für Ideone. Daher gilt das angegebene Beispiel für n = 18.)

TheBikingViking
quelle
0

Python 2, 207 Bytes

n,i,r,o=input(),1,[],[]
while len(o)<n:
 r+=[(lambda n:len(set(reduce(list.__add__,([i,n//i]for i in range(1,int(n**0.5)+1)if n%i==0)))))(i)];h=max(r)
 if r.index(h)>i-2 and r.count(h)<2:o+=[i]
 i+=1
print o

Verwendet die gleiche Methode wie Dennis 'Jelly-Antwort. Berechnet die ersten 20 Terme in <2Sekunden.

Zach Gates
quelle