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,2

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

Table of n, a(n) for n=1..67.

Luc Rousseau, Proof that the algorithm performs integer factorisation

Formula

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

Prog

(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);
}
}

Crossrefs

Cf. A020639, A032742.

Sequence in context: A052131 A329486 A051145 * A057495 A321366 A180246

Adjacent sequences: A288963 A288964 A288965 * A288967 A288968 A288969

Keyword

nonn

Author

Luc Rousseau, Jun 20 2017

Status

approved