Verständnisproblem mit Sets

Hi,
ich versuche gerade dieses Problem von Project Euler zu lösen:
https://projecteuler.net/problem=29

Ich bin von alleine leider nicht auf die Lösung gekommen, weiß aber jetzt dass die Lösung 9183 ist.
Obwohl ich den Code hab der mir diese Lösung gibt, verstehe ich nicht wie sie zustande kommt.
Ich habe mehrere Wege ausprobiert, und kam immer auf 997.
Hier der “richtige” Code:

Set<BigInteger> generated = new HashSet<BigInteger>();
        for (int a = 2; a <= 100; a++) {
            for (int b = 2; b <= 100; b++) {
                generated.add(BigInteger.valueOf(a).pow(b));
            }
        }

System.out.println(generated,size()); // output = 9183

Wie kann das sein? Es wird doch nur 99*99=9801 mal etwas geaddet, wie kann die size() dann größer sein? Vor allem dann wenn Duplikate rausfallen…

Und wo ist der Unterschied hierzu?

Set<Long> generated = new HashSet<Long>();
        for (int a = 2; a <= 100; a++) {
            for (int b = 2; b <= 100; b++) {
                generated.add((long) Math.pow(a, b));
            }
        }

        System.out.println(generated.size()); // output = 997

Ich steh ziemlich auf dem Schlauch gerade…

  1. 99*99=9801 und output = 9183 wieso sollte das nicht gehen?
  2. long hat einen Wertebereich bis +9.223.372.036.854.775.807 aber schon 50 ^ 12 ist 244.140.625.000.000.000.000 und damit zu groß für long. Dadurch hast du einfach mehr doppelte und dadurch ein kleineres Ergebnis.

Wie kann das sein? Es wird doch nur 99*99=9801 mal etwas geaddet, wie kann die size() dann größer sein? Vor allem dann wenn Duplikate rausfallen…

Size ist 9183 < 9801 :slight_smile:

Das Problem bei der 2. Version ist der Cast nach Long, Double hat durch die IEEE 754-Darstellung einen größeren Wertebereich als Long:

Long.Max_Value ist 9223372036854775807, den Wert erreichst du schon bei a=2, b=63

Bsp:

		double d2 = Math.pow(50, 59);
		System.out.println(d1 == d2); //false
		System.out.println(((long)d1) == ((long)d2)); //true```

//Zu langsam :cool:

Dass 100 ^ 100 zu groß ist hätte ich mir auch denken können, hab da garnicht drüber nachgedacht >.<
Und das andere war nur ein Zahlendreher, hab da wohl zu lange drauf gestarrt oO
merken: 9801 > 9183…

Danke :wink:

Es gibt noch eine andere Möglichkeit ohne BigIntegers verwenden zu müssen.

Jede Zahl lässt sich in ihre Primfaktoren zerlegen.
Um die Zahlen von 0 bis 100 darzustellen braucht es also nur ein Integer-Array mit 101 Feldern, welches die entsprechenden Koeffizienten vorhält.
Zwei wäre [0, 0, 1, 0, …]
Vier wäre [0, 0, 2, 0, …]
Sechs wäre [0, 0, 1, 1, …]

Wenn man nun die Potenz von 2 hoch 7 berechnen möchte, dann nimmt man sich eine in die Faktoren zerlegte zwei und multipliziert jeden Koeffizienten mit der Sieben
2^7 ist [0, 0, 2 * 7, 0, …]

Und jetzt benötigt man nur noch etwas um doppelte Arrays zu erkennen. Ich habe mich hier mal für eine Klasse entschieden in der ich das array ablege und mir equals + hashCode generieren lasse.

import java.util.HashSet;
import java.util.Set;

class SetEntry {
	int[] array;

	public SetEntry(int[] array) {
		this.array = array;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + Arrays.hashCode(array);
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		SetEntry other = (SetEntry) obj;
		if (!Arrays.equals(array, other.array))
			return false;
		return true;
	}

	@Override
	public String toString() {
		return Arrays.toString(array);
	}
}

public class Euler29 {

	public static int[] factorize(int n) {
		int[] result = new int[101];
		int value = n;
		int divisor = 2;
		while (divisor <= value) {
			if (value % divisor != 0) {
				divisor++;
			} else {
				result[divisor] = result[divisor] + 1;
				value = value / divisor;
			}
		}
		return result;
	}

	public static int[] pow(int a, int b) {
		int[] array = factorize(a);
		int[] result = new int[101];
		for (int i = 0; i < array.length; i++) {
			result** = array** * b;
		}
		return result;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Set<SetEntry> set = new HashSet<>();
		for (int i = 2; i <= 100; i++) {
			for (int j = 2; j <= 100; j++) {
				set.add(new SetEntry(pow(i, j)));
			}
		}
		System.out.println(set.size());
		System.out.println(new SetEntry(pow(15, 2)));
	}
}

Nur mal als ein Beispiel wie man das auch noch machen kann.