SHARE
TWEET

A001923

DulcetAirman Sep 22nd, 2017 (edited) 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package ch.claude_martin.playground;
  2.  
  3. import java.util.Map;
  4. import java.util.TreeMap;
  5. import java.util.stream.LongStream;
  6.  
  7. // see https://oeis.org/A001923
  8. public final class SomeClass {
  9.  
  10.     /**
  11.      * As solved by Muhammad.
  12.      */
  13.     static long f0(long n) {
  14.         long sum = 0;
  15.         for (int j = 1; j <= n; j++) {
  16.             sum += Math.pow(j, j);
  17.         }
  18.         return sum;
  19.     }
  20.  
  21.     /**
  22.      * Recursive.
  23.      */
  24.     static long f1(long n) {
  25.         if (n == 0L)
  26.             return 0L;
  27.         return power(n) + f1(n - 1);
  28.     }
  29.  
  30.     /** Stream API. */
  31.     static long f2(int n) {
  32.         return LongStream.rangeClosed(1, n).map(SomeClass::power).sum();
  33.     }
  34.  
  35.     /** Naive. */
  36.     static long f3(int n) {
  37.         long result = 0;
  38.         for (int i = 1; i <= n; i++)
  39.             result += power(i);
  40.         return result;
  41.     }
  42.  
  43.     /** Extra naive. */
  44.     static long f4(int n) {
  45.         if (n == 0)
  46.             return 0;
  47.         long result = 1;
  48.         for (int i = 2; i <= n; i++) {
  49.             long pow = 1;
  50.             for (int j = 0; j < i; j++)
  51.                 pow *= i;
  52.             result += pow;
  53.         }
  54.         return result;
  55.     }
  56.  
  57.     static final Map<Integer, Long> cache = new TreeMap<>();
  58.  
  59.     /** Cached, using {@link #f1(long)}. */
  60.     static long cached(int n) {
  61.         return cache.computeIfAbsent(n, SomeClass::f1);
  62.     }
  63.  
  64.     /** n<sup>n</sup>. */
  65.     static long power(final long number) {
  66.         long res = 1;
  67.         long sq = number;
  68.         long power = number;
  69.         while (power > 0) {
  70.             if (power % 2 == 1) {
  71.                 res *= sq;
  72.             }
  73.             sq = sq * sq;
  74.             power /= 2;
  75.         }
  76.         return res;
  77.     }
  78.  
  79.     public static void main(String[] args) {
  80.         for (int i = 0; i < 17; i++) {
  81.             long f0 = f0(i);
  82.             long f1 = f1(i);
  83.             long f2 = f2(i);
  84.             long f3 = f3(i);
  85.             long f4 = f4(i);
  86.             long cached = cached(i);
  87.             assert (f0 == f1) : f0 + " != " + f1;
  88.             assert (f0 == f2) : f1 + " != " + f2;
  89.             assert (f0 == f3) : f1 + " != " + f3;
  90.             assert (f0 == f4) : f1 + " != " + f4;
  91.             assert (f0 == cached) : f1 + " != " + cached;
  92.             System.out.print("A001923(");
  93.             System.out.print(i);
  94.             System.out.print(") = ");
  95.             System.out.print(f1);
  96.             System.out.println();
  97.         }
  98.         System.out.println();
  99.     }
  100. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top