Project Euler #29 Distinct powers

Of course brute force is easy, but for the 'right' solution, I failed to complete this, and found help from stackoverflow here as well as Project Euler forum. Here is the implementation of both approach:

import java.util.Scanner;

public class Solution5 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long N = scanner.nextLong();
        // System.out.println(getCount(N));
        System.out.println(better(N));
        scanner.close();
    }

    private static long getCount(long N) {
        long i, j, k;
        long SUM = (N - 1) * (N - 1);
        for (i = 2; i <= Math.sqrt(N); i++) {
            for (j = 2; j <= Math.log(N) / Math.log(i) + 1; j++) {
                k = (long) Math.pow(i, j);
                if (k > N) {
                    continue;
                }
                // cout << "i=" << i << " j=" << j << " k=" << k << endl;
                int factor = (int) (Math.log(k) / Math.log(j));
                long minus = (long) (N / j) - 1;
                if (minus < 0) {
                    minus = 0;
                }
                SUM -= minus;
                System.out.println("i=" + i + " j=" + j + " k=" + k + " minus=" + minus);
            }

        }
        return SUM;
    }

    private static long better(long M) {
        int maxPow = (int) Math.floor(Math.log(M) / Math.log(2));
        long[] dupesPerPow = new long[maxPow + 1];
        long[] numOfPow = new long[maxPow + 1];
        long totDupes = 0;

        // Step one: find dupes per power.
        for (int i = 2; i <= maxPow; i++) {
            boolean[] powOverlap = new boolean[(int) (M + 1)];
            for (int k = 1; k <= i - 1; k++) {
                int spacing = lcm(k, i) / i;
                for (int n = 0; n <= k * M / i; n += spacing) {
                    powOverlap[n] = true;
                }
            }
            long count = 0;
            for (int j = 2; j <= M; j++) {
                if (powOverlap[j])
                    count++;
            }
            dupesPerPow[i] = count;
        }

        // Step two: find actual number of powers.
        int sqrtN = (int) Math.pow(M, 0.5);
        boolean[] powersNotToRepeat = new boolean[sqrtN + 1];
        for (int i = 2; i <= sqrtN; i++) {
            if (!powersNotToRepeat[i]) {
                for (int p = 2; Math.pow(i, p) <= M; p++) {
                    numOfPow[p]++;
                    if (Math.pow(i, p) <= sqrtN)
                        powersNotToRepeat[(int) Math.pow(i, p)] = true;
                }
            }
        }

        for (int p = 2; p <= maxPow; p++) {
            totDupes += numOfPow[p] * dupesPerPow[p];
        }
        return (M - 1) * (M - 1) - totDupes;
    }

    public static int lcm(int k, int i) { // Use Euclidean algo for GCD to get LCM.
        // assert k < i
        if (i % k == 0)
            return i;
        else {
            int i_ = i;
            int k_ = k; // store original values
            int r = i % k;
            while (r != 0) {
                i = k;
                k = r;
                r = i % k;
            }
            return i_ * k_ / k;
        }
    }
}

// 2^2 2^3 2^4 2^5 2^6 2^7 2^8 2^9 2^10
// 3^2 3^3 3^4 3^5 3^6 3^7 3^8 3^9 3^10
// 4^2 4^3 4^4 4^5 4^6 4^7 4^8 4^9 4^10
// 5^2 5^3 5^4 5^5 5^6 5^7 5^8 5^9 5^10
// 6^2 6^3 6^4 6^5 6^6 6^7 6^8 6^9 6^10
// 7^2 7^3 7^4 7^5 7^6 7^7 7^8 7^9 7^10
// 8^2 8^3 8^4 8^5 8^6 8^7 8^8 8^9 8^10
// 9^2 9^3 9^4 9^5 9^6 9^7 9^8 9^9 9^10
// 10^2 10^3 10^4 10^5 10^6 10^7 10^8 10^9 10^10
// 10
// 2 - 4 4
// 2 - 8 2
// 3 - 9 4

MathJax test

When $a \ne 0$, there are two solutions to \(ax^2 + bx + c = 0\) and they are $$x = {-b \pm \sqrt{b^2-4ac} \over 2a}.$$ \(F_n = \lfloor\frac{\psi^n}{\sqrt{5}}\rfloor\), where \(\psi\) is \(\frac{1-\sqrt(5)}{2}\).
To find minimum D-digit \(F_n\) we can set \(F_n = \lfloor\frac{phi^n}{\sqrt(5)}\rfloor < 10^D\).
By taking log on both side, and we get \(n \cdot log(\psi) - log(\sqrt(5)) < D \cdot log(10)\)

Project Euler #28 Number spiral diagonals

First I solved with O(n), but I found O(1) and below is implementation of both:

import java.math.BigInteger;
import java.util.Scanner;

public class Solution4 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while (T-- > 0) {
            long N = scanner.nextLong();
            // System.out.println(bruteForce(N));
            System.out.println(muchBetter(N));
        }
        scanner.close();
    }

    private static String muchBetter(long n) {
        BigInteger bi = BigInteger.valueOf((n - 1) / 2);
        BigInteger bi1 = bi.pow(3).multiply(BigInteger.valueOf(16));
        BigInteger bi2 = bi.pow(2).multiply(BigInteger.valueOf(30));
        BigInteger bi3 = bi.multiply(BigInteger.valueOf(26)).add(BigInteger.valueOf(3));
        BigInteger answer = bi1.add(bi2).add(bi3).divide(BigInteger.valueOf(3)).mod(BigInteger.valueOf(1000000007L));
        return answer.toString();
    }

    private static long bruteForce(long n) {
        long SUM = 1;
        long end = 1;
        for (long i = 1; i <= n / 2; i++) {
            SUM += (4 * end + 20 * i);
            end = end + 8 * i;
            if (SUM > 1000000007L) {
                SUM %= 1000000007L;
            }
        }
        return SUM;
    }
}

Project Euler #27 Quadratic primes

Just try with the given condition. Self explanatory.
Used C++:

#include <iostream>
#include <cmath>

using namespace std;

int isPrime(int N);

int main()
{
    int i;
    int N, F, a, b, count;
    int MAX_COUNT=0, MAX_A=0, MAX_B=0;
    cin >> N;
    for (b=N; b>=-1*N; b--) {
        if (!isPrime(b)) {
            continue;
        }
        for (a=N; a>=-1*N; a--) {
            for(i=0; ;i++) {
                F = i * i + a*i + b;
                if (!isPrime(F)) {
                    if (i > MAX_COUNT) {
                        MAX_COUNT = i;
                        MAX_A = a;
                        MAX_B = b;
                    }
                    break;
                }
            }
        }
    }
    cout << MAX_A << " " << MAX_B << endl;
}

int isPrime(int N)
{
    int i;
    if (N < 2) return 0;
    if (N == 2) return 1;
    for (i=3; i<=sqrt(N); i+=2) {
        if (N%i == 0) {
            return 0;
        }
    }
    return 1;
}

Project Euler #25 1000-digit Fibonacci number

First I attempted to solve this problem using BigInteger & BigDecimal using bruteforce method, but come on! We know Euler didn't know how to import such classes.
Asymptotically, and precisely, we can get n-th term of Fibonacci number using following formular. Again, I am not going to talk about how to prove this, but for those of who are interested, please take a look at Wikipedia here and Wolfram Alpha here

Basic idea is as follows. I will use LaTex format for mathematical formula from now on.

1. \(F_n = \lfloor\frac{\psi^n}{\sqrt{5}}\rfloor\), where \(\psi\) is \(\frac{1-\sqrt(5)}{2}\).
2. To find minimum D-digit \(F_n\) we can set \(F_n = \lfloor\frac{phi^n}{\sqrt(5)}\rfloor < 10^D\).
3. By taking log on both side, and we get \(n \times \log{\psi} - \log{\sqrt{5}} < D \times \log{10}\)

Using 3., we will iterate from digit 1 to 5000 to find minimum F_n which satisfies the above formula. That's it. O(n).

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;

public class Solution3 {

    private static int DATA[] = new int[5002];
    private static int DATA2[] = new int[5002];

    private static void bruteForce() {
        BigInteger bi1 = BigInteger.valueOf(1);
        BigInteger bi2 = BigInteger.valueOf(1);
        BigInteger bi3;
        int term = 3;
        int digit = 1;
        int cur;
        DATA[1] = 1;
        while (digit <= 5000) {
            bi3 = bi1.add(bi2);
            cur = bi3.toString().length();
            if (cur > digit) {
                System.out.println(term);
                ;
                digit = cur;
                DATA[digit] = term;
            }
            bi1 = bi2;
            bi2 = bi3;
            term++;
        }

        int T, N;
        Scanner scanner = new Scanner(System.in);
        T = scanner.nextInt();
        while (T-- > 0) {
            N = scanner.nextInt();
            System.out.println(DATA[N]);
        }
        scanner.close();
    }

    public static void main(String[] args) {
        // bruteForce();
        approximate();
    }

    private static void approximate() {
        int T, N;
        final double OMEGA = (1 + Math.sqrt(5)) / 2;
        // F_n <= Omega^n / sqrt(5) + 0.5 < 10^digit
        // log (F_N) <= n * log(Omega) - log(sqrt(5)) < digit * log 10
        // For digit 1 ... 5000, find n argmax (n * log(Omega) - log(sqrt(5)))

        int term = 1;
        double fn;
        for (int i = 1; i <= 5000; i++) {
            double l = (i * Math.log(10));
            // System.out.println("L=" + l);
            do {
                fn = term * Math.log(OMEGA) - Math.log(Math.sqrt(5));
                // System.out.println("F_" + term + "= " + fn);
                term++;
            } while (l > fn);
            DATA2[i] = term - 1;
        }
        Scanner scanner = new Scanner(System.in);
        T = scanner.nextInt();
        while (T-- > 0) {
            N = scanner.nextInt();
            System.out.println(DATA2[N - 1]);
        }
        scanner.close();
    }
}