Folge A005185 in OEIS berechnen

Java-Forum Allgemeine Themen
1

Ich soll die 1 Milliardste Q-Zahl der Hofstadter-Folge berechnen …

Leider hält meine Implementierung nicht an. Was mache ich falsch?

public class A005185 {
    public static int q(int n) {
        if (n <= 2) {
            return 1;
        }
        return q(n - q(n - 1)) + q(n - q(n - 2));
    }

    public static int q_cache(int n) {
        int[] cache = new int[n + 2];
        cache[1] = 1;
        cache[2] = 1;
        for (int i = 3; i <= n; i++) {
            cache[i] = cache[i - cache[i - 1]] + cache[i - cache[i - 2]];
        }
        return cache[n];
    }

    public static void main(String[] args) {
        for (int i = 1; i <= 20; i++) {
            System.out.println("Q(" + i + ") = " + q(i));
        }
        System.out.println();
        for (int i = 1; i <= 20; i++) {
            System.out.println("Q(" + i + ") = " + q_cache(i));
        }
        System.out.println();
        for (int i = 1; i <= 1_000_000_000; i *= 10) {
            System.out.println("Q(" + i + ") = " + q_cache(i));
        }
    }
}
2

Sorry, das hält doch an … man muss nur eine Minute warten.

Wie berechnet man die 1 Billionstel Q-Zahl?

3

Mit long, und viel Zeit :no_mouth:

1 Like
4

Warum ginge das eigentlich nicht?

    public static int q_cache_fixed_size(int n) {
        int[] cache = new int[4];
        cache[1] = 1;
        cache[2] = 1;
        cache[3] = 1;
        for (int i = 3; i <= n; i++) {
            cache[0] = cache[1];
            cache[1] = cache[2];
            cache[2] = cache[3];
            cache[3] = cache[3 - cache[2]] + cache[3 - cache[1]];
        }
        return cache[3];
    }

IOOBE ab Q(7) …

5

Ok, blöde Frage gewesen. :no_mouth:

1 Like