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