0 Daumen
1,2k Aufrufe

Aufgabe:

Finde die kleinste natürliche Zahl n, sodass der ggT von p(n) und p(n^3) keine Zweierpotenz (einschließlich 1) ist.


Problem/Ansatz:

Es sei p(k) die Anzahl aller positiven Teiler einer natürlichen Zahl k.

Ermittle die kleinste natürliche Zahl n, sodass der ggT von p(n) und p(\( n^{3} \)) keine Zweierpotenz (einschließlich 1) ist.

Die Anzahl der Teiler einer Zahl kann man ja über die Primfaktorzerlegung bestimmen. Also die Exponenten aller Faktoren jeweils mit 1 addieren und diese Summen dann multiplizieren.

Vielleicht kann man darauf aufbauen ?

Ansonsten weiß ich nicht, wie man diese Aufgabe lösen könnte.

Dankeschön für alle Beiträge schon mal!

Avatar von

Mir ist selbst eine Eigenschaft eingefallen. Ist n keine Quadratzahl, so hat sie eine gerade Anzahl an Teilern. Folglich ist ist auch die Anzahl der Teiler von n^3 gerade. Da 2 die einzige gerade Primzahl ist, wird der ggT von p(n) und p(n^3) nie ohne Zweierpotenz dargestellt werden können. n ist folglich eine Quadratzahl.

Macht das Sinn, bzw. ist das richtig ?

Ja, das stimmt.

Nicht ganz. Den mir scheint, das es erlaubt ist, dass ( 2^n)*x der ggT ist .

Wenn ich das richtig verstanden habe, ist zum Beispiel 6 als ggT erlaubt.

Ja, ich habe die letzte Folgerung übersehen und nicht weiter beachtet - die ist natürlich falsch. Dass die Zahl gerade sein muss, stimmt aber.

Ich möchte mich bei allen Teilhabenden bedanken! Die Lösung erscheint nach der Erklärung wie meist logisch xD

3 Antworten

0 Daumen
 
Beste Antwort

Hässlich aber geht:

1. \( n \) kann keine Primzahlpotenz sein:

Ist \( n = p^e\), dann ist \( n^3 = p^{3e} \). Die Teilerzahlen sind \( e + 1 \) und \( 3e + 1 \). Ist \( t \) ein gemeinsamer Teiler dieser Anzahlen, so gilt auch \( t \mid 3 \cdot (e+1) \) und folglich teilt \( t \) auch die Differenz \( 3(e+1) - (3e + 1) = 2 \) \( \implies t \in \{ 1, 2 \} \).

=> n muss mindestens 2 Primfaktoren besitzen.

2. \( n = p^e \cdot q^f \) mit p, q Primzahlen, e, f > 0. Man kann annehmen, dass \( e \ge f \) ist, um sich doppelte Rechnungen zu sparen. Wir machen eine Tabelle:

$$ \begin{array}{c|c|c|c|c|c} e & f & (e+1)(f+1) & (3e+1)(3f+1) & \text{ggT} & \\\hline 1 & 1 & \color{red} 4 & - & - & \\ 2 & 1 & 6 & 28 & 2 & \\ 2 & 2 & 9 & 49 & 1 & \\ 3 & 1 & 8 & 40 & 8 & \\ 3 & 2 & 12 & 70 & 2 & \\ 3 & 3 & \color{red} {16} & - & - & \\ 4 & 1 & 10 & 52 & 2 & \\ 4 & 2 & 15 & 91 & 1 & \\ 4 & 3 & 20 & 130 & 10 & \checkmark \rightarrow 2^4 \cdot 3^3 = 432 \\ 5 & 1 & 12 & \color{red}{64} & - & \\ 5 & 2 & 18 & 112 & 2 & \\ 6 & 1 & 14 & 76 & 2 & \\ 6 & 2 & 21 & 133 & 7 & \checkmark \rightarrow 2^6 \cdot 3^2 = 576 \\ 7 & 1 & \color{red}{16} & - & - & \\ 8 & 1 & - & - & - & \color{red}{2^8 \cdot 3^1 > 432} \\ \end{array} $$

Alle überflüssigen Zeilen habe ich ausgelassen. Wenn du weißt, dass \( e = 4 \), \( f = 3 \) funktioniert musst du z.B. nicht mehr \( e = 5,f = 3,4,5\) versuchen, da diese Zahlen größer ein müssen als bei \( e = 4 \), \( f = 3 \). Wenn du bei einer der Teileranzahlen eine Zweipotenz erhältst, ist auch der ggT eine Zweierpotenz, die restlichen Zellen kann man sich also sparen. Bei einem Treffer setzen wir \( p = 2 \) und \( q = 3 \) um die kleinste Zahl zu diesen Exponenten zu erhalten.

=> 432 ist die kleinste solche Zahl mit 2 Primfaktoren.

Selbes Spiel für 3 Faktoren

\( n = p_1^{e_1} p_2^{e_2} p_3^{e_3} \) mit \( e_1 \ge e_2 \ge e_3 \)

$$ \begin{array}{c|c|c|c|c|c} e_1 & e_2 & e_3 & (e_1+1)(e_2+1)(e_3+1) & (3e_1+1)(3e_2+1)(3e_3+1) & \text{ggT} & \\\hline 1 & 1 & 1 & 8 & - & - & \\ 2 & 1 & 1 & 12 & 112 & 4 & \\ 2 & 2 & 1 & 18 & 196 & 2 & \\ 2 & 2 & 2 & 27 & 343 & 1 & \\ 3 & 1 & 1 & 16 & - & - & \\ 3 & 2 & 1 & 24 & 280 & 8 & \\ 3 & 2 & 2 & 36 & 490 & 2 & \\ 3 & 3 & 1 & 32 & - & - \\ 3 & 3 & 2 & 48 & 700 & 4 & \\ 3 & 3 & 3 & 64 & - & - & \\ 4 & 1 & 1 & 20 & 208 & 4 & \end{array}$$

Hier können wir stoppen, denn \( 2^4 \cdot 3^2 \cdot 5 > 432 \) und \( 2^5 \cdot 3 \cdot 5 > 432 \)

und für 4 Faktoren:

$$ \begin{array}{c|c|c|c|c|c} e_1 & e_2 & e_3 & e_4 & \prod (e_i+1) & \prod (3e_i+1) & \text{ggT} & \\\hline 1 & 1 & 1 & 1 & 16 & - & - \\ 2 & 1 & 1 & 1 & 24 & 448 & 8 & \end{array}$$

Auch hier können wir stoppen, denn \( 2^3 \cdot 3 \cdot 5 \cdot 7 > 432 \) und \( 2^2 \cdot 3^2 \cdot 5 \cdot 7 > 432 \).

Mehr als 5 können es nicht sein, denn \( 2\cdot3\cdot 5 \cdot 7 \cdot 11 >432 \).

Insgesamt kommt man zu dem Schluss, dass 432 die kleinste dieser Zahlen sein muss.

Avatar von 1,3 k

Ja, das kann ich bestätigen, 432 ist die kleinste die ich gefunden habe, darum kann der Exponent der 2 bis maximal 8 gehen , doch da finden wir keine Lösung. Der Exponent der 3 geht bis maximal 5 auch dort gibt es keine Lösung. Also muss es eine Kombination sein, doch auch dort finden wir nichts besseres

0 Daumen

Die kleinste Zahl ist 432

$$n=2^4*3^3=432$$$$P(n)= 5*4=20$$$$n^3=2^{12} * 3^{9}$$$$P( n^3)= 13*10$$$$ggT(P(n^3);P(n))=5$$

Es gibt keine kleinere Zahl

Denn 2^n ;n<9 ist es nicht

3^n; n<5 ist es auch nicht

Und für 2^m*3^n gibt es in dem Bereich auch keine bessere Lösung.






Zur Erinnerung $$n=2^8*3^4=20736$$$$P(n)= 9*5=45$$$$n^3=2^{24} * 3^{12}$$$$P( n^3)= 25*13$$$$ggT(P(n^3);P(n))=5$$

Kleiner ist

$$n=2^6*3^2=576$$$$P(n)= 7*3=21$$$$n^3=2^{18} * 3^{6}$$$$P( n^3)= 19*7$$$$ggT(P(n^3);P(n))=7$$

Avatar von 11 k
Finde die kleinste natürliche Zahl n, sodass der ggT von p(n) und p(n^3) keine Zweierpotenz (einschließlich 1) ist.
ggT(2;4)=2 = \( \color{red}{2^1} \)

Danke, alles klar, ich lösche den Beitrag.

20736 werfe ich ins Rennen, sehr klein ist sie nicht. Siehe Antwort

Ob es noch kleinere gibt, kann ich nicht sagen.

Wie sind Sie auf dieses n gekommen ?

Die Frage ist aber gerade "Ermittle die kleinste natürliche Zahl n, sodass der ggT von p(n) und p(n3) keine Zweierpotenz (einschließlich 1) ist.". Deshalb wird diese Antwort dem Fragesteller nicht unbedingt weiterhelfen.

Richtig, 576 ist schon kleiner,

Wer bietet weniger?

Doktor POW,

Ich habe mir eine Liste gemacht,

Exponent ; Teiler; Exponent *3;Teiler

1 ; 2 ; 3 ; 4

2; 3 ; 6 ; 7

3; 4 ; 9 ;10

................

m; m+1 ; 3m ; 1+3m

die geraden Zahlen in der letzten Spalte, machen uns immer die Probleme.

Nun dachte ich erst falsch, dass die Zahl keine Primzahl sein dürfte, darum bin ich auf 25 gekommen, doch es reicht ja aus, dass die Zahl selbst der Teiler ist, darum die verflixte 7 .Dazu musste ich nur noch in der 2 Spalte auch eine 7 finden ( bei 25 die 5)

Hogar,

danke für die Erklärung.

Jetzt sind  nur noch 432 zu unterbieten. Siehe Antwort

0 Daumen

Da die Potenz \(2^0=1\) durch die Aufgabestellung ausgeschlossen ist, kann man die triviale Lösung für \(n=1\) natürlich nicht verwenden.

Deshalb habe ich Mal ein kleines Java-Programm gemacht, womit man die kleinste natürliche Zahl, die die Aussage erfüllt, auch ganz schnell herausfinden kann. Das Programm ist relativ simpel. Die Scanner-Klasse dient zum Eingeben einer Zahl, ab die man mit dem Finden einer Zahl starten will. In der Funktion factor werden die Anzahl der Divisoren berechnet. Mit findGCD berechnen wir den ggT durch die Benutzung der Modulo-Operation. In findnumber werden schließlich iterativ alle Zahlen durchprobiert und zu jeder Zahl die Anzahl der Faktoren und der ggT berechnet. Wenn der ggT dann eine Zweierpotenz ist, bricht das Programm ab und gibt die Zahl n aus. In unserem Fall wird Die kleinste Zahl ist 432 ausgegeben.

Vorteil hiervon ist, dass du auch Zahlen größer als 432 eingeben kannst und so jeweils die nächsten möglichen Zahlen findest. So finden wir auch \(576,648,1296,2000,\ldots\) heraus.

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);
      System.out.println("Zahl eingeben");

      double number = scanner.nextDouble();
      double smallestnumber = findNumber(number);
      System.out.println("Die kleinste Zahl ist " + smallestnumber);
  }

  public static double factor(double number) {
      int counter;
      counter = 0;
      for (int i = 1; i <= Math.sqrt(number); i++)
          if (number % i == 0 && i * i != number) {
              counter = counter + 2;
          } else if (i * i == number) {
              counter++;
          }
      return counter;
  }

  public static double findGCD(double a, double b) {
      if (b == 0)
          return a;
      return findGCD(b, a % b);
  }

  public static double findNumber(double number2) {
      double gcd;
      double fctr1;
      double fctr2;
      double number;

      for (number = number2; number < 10000; number++) {
          fctr1 = factor(number);
          fctr2 = factor(Math.pow(number, 3.0));
          gcd = findGCD(fctr1, fctr2);
          if (!(istZweierpotenz((int) gcd)) && gcd != 2.0 && gcd != 1.0) {
              return number;
          }
      }
      return number;
  }

  static boolean istZweierpotenz(long x) {
      double zweierLogarithmus = Math.log(x) / Math.log(2.0);
      int gerundeterZweierLogarithmus = (int) (zweierLogarithmus + 0.5); // runden
      return potenz(2, gerundeterZweierLogarithmus) == x;
  }

  static long potenz(int basis, int exponent) {
      if (0 >= exponent) {
          return 1;
      }
      if (istGerade(exponent)) {
          return potenz(basis * basis, exponent / 2);
      } else {
          return basis * potenz(basis * basis, (exponent - 1) / 2);
      }
  }

  static boolean istGerade(int x) {
      return 0 == x % 2;
  }
}

Avatar von 2,1 k

Ich dachte 2^0 ist eine Zweierpotenz... ich schreib es auf jeden Fall mit auf, vielen Dank für die Hilfe.

In der Aufgabenstellung war doch geschrieben, dass die 2er-Potenzen einschließlich \(2^1=2\) gemeint sind, oder? Oder meinen sie mit einschließlich 1 wirklich \(2^0=1\)? Also geht es hier um \(2^x\) mit \(x=1\) oder um \(2^x=1\) mit \(x=0\)?

Oder meinen sie mit einschließlich 1 wirklich 2^0=1?

Ja natürlich meint der Aufgabensteller das so, sonst ist die Aufgabe doch völlig trivial und damit auch ziemlich sinnlos.

Ich gehe davon aus, dass es die 1 nicht sein darf.

"Ermittle die kleinste natürliche Zahl n, sodass der ggT von p(n) und p(n3) keine Zweierpotenz (einschließlich 1) ist."

Damit könntest du zumindest nicht mehr unterboten werden, falls die 1 erlaubt ist .

Ja, die Aufgabe hätte dann wenig Sinn. Das stimmt xD

Hey DoctorPow, da meine Antwort ja leider ausgeschlossen war durch die Aufgabenstellung, habe ich meine Lösung angepasst und dir eine eher technische Lösung hinzugepackt. Diese Antwort sollte noch den nötigen Mehrwert zur Antwort von MatHaeMatician bringen, der das ganze ja sehr detailliert erklärt hat.

Wo ist denn meine 20736 geblieben, durch die sind wir doch auf das Ganze gekommen.

;-)

Haha :) \({}{}\)

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community