Skip to content

Instantly share code, notes, and snippets.

@helospark
Created January 5, 2024 12:35
Show Gist options
  • Save helospark/594a8e2a8a3ac3822a5b59908259bdb6 to your computer and use it in GitHub Desktop.
Save helospark/594a8e2a8a3ac3822a5b59908259bdb6 to your computer and use it in GitHub Desktop.
Finds multiplicative persistance numbers
/**
* Finds multiplicative persistance numbers.
* Due to parallel nature, it sometimes not finding the smallest possible multiplicative persistance numbers
* Video: https://www.youtube.com/watch?v=Wim9WJeDTHQ
* Oeis: https://oeis.org/A003001
*/
package com.test;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
public class MultiplicationPersistance {
private static volatile int RECORD = 2;
private static final int SEARCH_START_DIGITS = 3;
private static final int SEARCH_END_DIGITS = 100000;
static int[] INDICES_TO_INCREASE = new int[] { 9, 8, 7, 6, 4, 3, 2 };
public static void main(String[] args) {
long start = System.currentTimeMillis();
findAllParallel();
long end = System.currentTimeMillis();
System.out.println("Took " + ((end - start) / 1000.0));
// findOne();
// verifyOne();
}
public static void verifyOne() {
int[] comp = new int[10];
comp[2] = 4;
comp[3] = 20;
comp[7] = 5;
verifyLength(comp);
}
private static void findOne() {
int[] components = new int[10];
Arrays.fill(components, 0);
components[INDICES_TO_INCREASE[0]] = 18;
int max = generateNumberRecursive(components, 0);
System.out.println("Max: " + max);
}
public static void findAllParallel() {
List<CompletableFuture<?>> futures = new ArrayList<>();
ExecutorService pool = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
for (int i = SEARCH_START_DIGITS; i < SEARCH_END_DIGITS; ++i) {
int length = i;
CompletableFuture<Void> future = CompletableFuture.runAsync(() -> {
int[] components = new int[10];
Arrays.fill(components, 0);
components[INDICES_TO_INCREASE[0]] = length;
int max = generateNumberRecursive(components, 0);
System.out.println("Checked " + length + " length, max " + max);
}, pool);
futures.add(future);
}
futures.stream().forEach(future -> future.join());
pool.shutdown();
}
private static int generateNumberRecursive(int[] input, int index) {
int[] result = copyArray(input);
int currentMax = verifyLength(result);
int componentToChange = INDICES_TO_INCREASE[index];
while (result[componentToChange] > 0) {
result[componentToChange] -= 1;
int indexOffset = 1;
while (index + indexOffset < INDICES_TO_INCREASE.length && INDICES_TO_INCREASE[index + indexOffset] < 6) {
if (result[INDICES_TO_INCREASE[index + indexOffset]] >= 1) {
++indexOffset;
} else {
break;
}
}
if (index + indexOffset < INDICES_TO_INCREASE.length) {
result[INDICES_TO_INCREASE[index + indexOffset]] += 1;
} else {
result[componentToChange] += 1;
return currentMax;
}
if (index < INDICES_TO_INCREASE.length - 1) {
int currentLength = generateNumberRecursive(result, index + 1);
if (currentLength > currentMax) {
currentMax = currentLength;
}
} else {
int currentLength = verifyLength(result);
if (currentLength > currentMax) {
currentMax = currentLength;
}
}
}
return currentMax;
}
public static int[] copyArray(int[] input) {
int[] result = new int[10];
for (int i = 0; i < 10; ++i) {
result[i] = input[i];
}
return result;
}
private static int verifyLength(int[] result) {
BigInteger bigInteger = BigInteger.ONE;
for (int i = 0; i < result.length; ++i) {
for (int j = 0; j < result[i]; ++j) {
bigInteger = bigInteger.multiply(BigInteger.valueOf(i));
}
}
int count = 1;
while (bigInteger.compareTo(BigInteger.TEN) > 0) {
char[] charts = bigInteger.toString().toCharArray();
bigInteger = BigInteger.ONE;
for (int i = 0; i < charts.length; ++i) {
bigInteger = bigInteger.multiply(BigInteger.valueOf(charts[i] - '0'));
}
++count;
}
// System.out.println(toNum(result) + " " + Arrays.toString(result) + " " + count + " " + RECORD);
if (count > RECORD) {
RECORD = count;
System.out.println("RECORD(" + RECORD + ") " + toNum(result) + " " + Arrays.toString(result));
}
return count;
}
private static String toNum(int[] result) {
String num = "";
for (int i = 0; i < result.length; ++i) {
for (int j = 0; j < result[i]; ++j) {
num += ((i) + "");
}
}
return num;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment