cp's OEIS Frontend

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

%I A288966 #22 Mar 15 2024 07:24:42
%S A288966 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 A288966 15,56,16,60,17,24,18,32,19,72,20,28,21,80,22,84,23,32,24,92,25,48,26,
%U A288966 36,27,104,28,48,29,40,30,116,31,120,32,44,33,56,34,132
%N A288966 a(n) = the number of iterations the "HyperbolaTiles" algorithm takes to factorize n.
%C A288966 The provided "HyperbolaTiles" algorithm computes a factorization of n and computes a(n), the number of required iterations to reach this factorization.
%C A288966 If n = 1, the factorization is considered reached with (n=1*1).
%C A288966 If n is prime, the factorization is considered reached with (n=n*1).
%C A288966 If n is composite, the exhibited factorization is (n=p*q) with p least prime divisor of n.
%H A288966 Luc Rousseau, <a href="/A288966/a288966.pdf">Proof that the algorithm performs integer factorisation</a>
%F A288966 Conjecture: a(n) = n + A020639(n) - A032742(n) - 1, for n > 1. - _Ridouane Oudra_, Mar 12 2024
%o A288966 (Java)
%o A288966 package oeis;
%o A288966 public class A {
%o A288966 public static void main(String[] args) {
%o A288966 for (int n = 1; n <= 67; n ++) { hyberbolaTiles(n); }
%o A288966 }
%o A288966 private static void hyberbolaTiles(int n) {
%o A288966 int i = 0, x = 0, y = 0, p = 0, q = n;
%o A288966 do {
%o A288966 i ++;
%o A288966 if (y < 0) { x = y + q; q --; }
%o A288966 if (y > 0) { p ++; x = y - p; }
%o A288966 if (y == 0) {
%o A288966 p ++;
%o A288966 x = 0;
%o A288966 if ((p != 1) || (q == 1)) {
%o A288966 System.out.print("" + i + " // " + n + " = " + p + " * " + q);
%o A288966 break;
%o A288966 }
%o A288966 q --;
%o A288966 }
%o A288966 y = x + p - q;
%o A288966 } while (q > 0);
%o A288966 }
%o A288966 }
%Y A288966 Cf. A020639, A032742.
%K A288966 nonn
%O A288966 1,2
%A A288966 _Luc Rousseau_, Jun 20 2017