%I #22 Mar 15 2024 07:24:42

%S 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,

%T 15,56,16,60,17,24,18,32,19,72,20,28,21,80,22,84,23,32,24,92,25,48,26,

%U 36,27,104,28,48,29,40,30,116,31,120,32,44,33,56,34,132

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

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

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

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

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

%H Luc Rousseau, <a href="/A288966/a288966.pdf">Proof that the algorithm performs integer factorisation</a>

%F Conjecture: a(n) = n + A020639(n) - A032742(n) - 1, for n > 1. - _Ridouane Oudra_, Mar 12 2024

%o (Java)

%o package oeis;

%o public class A {

%o public static void main(String[] args) {

%o for (int n = 1; n <= 67; n ++) { hyberbolaTiles(n); }

%o }

%o private static void hyberbolaTiles(int n) {

%o int i = 0, x = 0, y = 0, p = 0, q = n;

%o do {

%o i ++;

%o if (y < 0) { x = y + q; q --; }

%o if (y > 0) { p ++; x = y - p; }

%o if (y == 0) {

%o p ++;

%o x = 0;

%o if ((p != 1) || (q == 1)) {

%o System.out.print("" + i + " // " + n + " = " + p + " * " + q);

%o break;

%o }

%o q --;

%o }

%o y = x + p - q;

%o } while (q > 0);

%o }

%o }

%Y Cf. A020639, A032742.

%K nonn

%O 1,2

%A _Luc Rousseau_, Jun 20 2017