A332810 Number of integers in range 1..n that are not encountered on any of the possible paths from n to 1 when iterating with nondeterministic map k -> k - k/p, where p is any prime factor of k.

0, 0, 0, 1, 1, 1, 1, 4, 3, 4, 4, 5, 5, 5, 5, 11, 11, 9, 9, 12, 9, 12, 12, 15, 16, 15, 17, 16, 16, 16, 16, 26, 16, 26, 17, 24, 24, 24, 24, 30, 30, 25, 25, 31, 27, 31, 31, 37, 31, 38, 37, 38, 38, 40, 39, 41, 40, 41, 41, 42, 42, 42, 43, 57, 43, 43, 43, 58, 43, 46, 46, 57, 57, 57, 54, 58, 47, 58, 58, 68, 66, 68, 68, 62, 69, 62, 62, 72, 72

Offset: 1

Author

Antti Karttunen, Apr 04 2020

Keywords

• nonn

Examples

			a(12): we have three alternative paths: {12, 8, 4, 2, 1}, {12, 6, 4, 2, 1} or {12, 6, 3, 2, 1}, with [5, 7, 9, 10, 11] being the only numbers in range 1..12 that do not occur in any of those paths, therefore a(12) = 5.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..20000

Crossrefs

Cf. A064097, A332809, A333123.

Programs

PARI

up_to = 105;
A332809list(up_to) = { my(v=vector(up_to)); v[1] = Set([1]); for(n=2,up_to, my(f=factor(n)[, 1]~, s=Set([n])); for(i=1,#f,s = setunion(s,v[n-(n/f[i])])); v[n] = s); apply(length,v); }
v332809 = A332809list(up_to);
A332810(n) = (n-v332809[n]);

Formula

a(n) = n - A332809(n).