A288966 a(n) = the number of iterations the "HyperbolaTiles" algorithm takes to factorize n.

1, 2, 4, 3, 8, 4, 12, 5, 8, 6, 20, 7, 24, 8, 12, 9, 32, 10, 36, 11, 16, 12, 44, 13, 24, 14, 20, 15, 56, 16, 60, 17, 24, 18, 32, 19, 72, 20, 28, 21, 80, 22, 84, 23, 32, 24, 92, 25, 48, 26, 36, 27, 104, 28, 48, 29, 40, 30, 116, 31, 120, 32, 44, 33, 56, 34, 132

Offset: 1

Author

Luc Rousseau, Jun 20 2017

Keywords

• nonn

Comments

The provided "HyperbolaTiles" algorithm computes a factorization of n and computes a(n), the number of required iterations to reach this factorization.

If n = 1, the factorization is considered reached with (n=1*1).

If n is prime, the factorization is considered reached with (n=n*1).

If n is composite, the exhibited factorization is (n=p*q) with p least prime divisor of n.

Links

• Luc Rousseau, Proof that the algorithm performs integer factorisation

Crossrefs

Cf. A020639, A032742.

Programs

Java

package oeis;
public class A {
public static void main(String[] args) {
for (int n = 1; n <= 67; n ++) { hyberbolaTiles(n); }
}
private static void hyberbolaTiles(int n) {
int i = 0, x = 0, y = 0, p = 0, q = n;
do {
i ++;
if (y < 0) { x = y + q; q --; }
if (y > 0) { p ++; x = y - p; }
if (y == 0) {
p ++;
x = 0;
if ((p != 1) || (q == 1)) {
System.out.print("" + i + " // " + n + " = " + p + " * " + q);
break;
}
q --;
}
y = x + p - q;
} while (q > 0);
}
}

Formula

Conjecture: a(n) = n + A020639(n) - A032742(n) - 1, for n > 1. - Ridouane Oudra, Mar 12 2024