A029827 Composite connected numbers: composite numbers k such that g(k) < g(u) + g(v) holds for all relatively prime factorizations k=u*v, where g(x) = ceiling(log_2 x).

15, 45, 51, 55, 57, 63, 85, 95, 99, 111, 115, 117, 119, 123, 153, 171, 185, 187, 201, 205, 207, 209, 213, 215, 219, 221, 225, 231, 235, 237, 245, 247, 249, 253, 255, 323, 333, 335, 355, 365, 369, 387, 391, 393, 395, 405, 407, 411, 415, 417, 423, 425, 429

Offset: 1

Author

Labos Elemer

Keywords

• nonn

Comments

Prime powers are not connected since they have no relatively prime factorizations. - Michel Marcus, Feb 25 2014

Examples

			k = 46665 = 5*9*17*61 is not a connected number because k = 61*765, but 16 >= 6 + 10.
		

References

• E. Labos, Spike Generating Dynamical Systems and Networks, In Lect. Notes in Economics and Mathematical Systems, pp. 189-206. Springer Verlag 1985.

Crossrefs

Cf. A029837, A036381-A036390, A034444.

Programs

PARI

g(n) = ceil(log(n)/log(2));
isok(n) = {if (isprime(n), return (0)); d = divisors(n); gn = g(n); bpf = 0; for (i=2, #d-1, di = d[i]; if (gcd(di, n/di)==1, bpf = 1; if (gn >= g(di)+g(n/di), return (0)););); return (bpf);} \\ Michel Marcus, Feb 25 2014

Extensions

a(40) corrected by Sean A. Irvine, Mar 05 2020