A333123
Consider the mapping k -> (k - (k/p)), where p is any of k's prime factors. a(n) is the number of different possible paths from n to 1.
Original entry on oeis.org
1, 1, 1, 1, 1, 2, 2, 1, 2, 2, 2, 3, 3, 5, 5, 1, 1, 5, 5, 3, 10, 5, 5, 4, 3, 7, 5, 9, 9, 12, 12, 1, 17, 2, 21, 9, 9, 14, 16, 4, 4, 28, 28, 9, 21, 14, 14, 5, 28, 7, 7, 12, 12, 14, 16, 14, 28, 23, 23, 21, 21, 33, 42, 1, 33, 47, 47, 3, 61, 56, 56, 14, 14, 23, 28, 28, 103, 42, 42, 5
Offset: 1
a(1): {1}, therefore a(1) = 1;
a(6): {6, 4, 2, 1} or {6, 3, 2, 1}, therefore a(6) = 2;
a(12): {12, 8, 4, 2, 1}, {12, 6, 4, 2, 1} or {12, 6, 3, 2, 1}, therefore a(12) = 3;
a(14): {14, 12, 8, 4, 2, 1}, {14, 12, 6, 4, 2, 1}, {14, 12, 6, 3, 2, 1}, {14, 7, 6, 4, 2, 1} or {14, 7, 6, 3, 2, 1}, therefore a(14) = 5.
From _Antti Karttunen_, Apr 05 2020: (Start)
For n=15 we have five alternative paths from 15 to 1: {15, 10, 5, 4, 2, 1}, {15, 10, 8, 4, 2, 1}, {15, 12, 8, 4, 2, 1}, {15, 12, 6, 4, 2, 1}, {15, 12, 6, 3, 2, 1}, therefore a(15) = 5. These form a graph illustrated below:
15
/ \
/ \
10 12
/ \ / \
/ \ / \
5 8 6
\_ | __/|
\__|_/ |
4 3
\ /
\ /
2
|
1
(End)
-
a[n_] := Sum[a[n - n/p], {p, First@# & /@ FactorInteger@n}]; a[1] = 1; (* after PARI coding by Rémy Sigrist *) Array[a, 70]
(* view the various paths *)
f[n_] := Block[{i, j, k, p, q, mtx = {{n}}}, Label[start]; If[mtx[[1, -1]] != 1, j = Length@ mtx; While[j > 0, k = mtx[[j, -1]]; p = First@# & /@ FactorInteger@k; q = k - k/# & /@ p; pl = Length@p; If[pl > 1, Do[mtx = Insert[mtx, mtx[[j]], j], {pl - 1}]]; i = 1; While[i < 1 + pl, mtx[[j + i - 1]] = Join[mtx[[j + i - 1]], {q[[i]]}]; i++]; j--]; Goto[start], mtx]]
-
for (n=1, #a=vector(80), print1 (a[n]=if (n==1, 1, vecsum(apply(p -> a[n-n/p], factor(n)[,1]~)))", ")) \\ Rémy Sigrist, Mar 11 2020
A332809
Number of distinct integers encountered on possible paths from n to 1 when iterating the nondeterministic map k -> k - k/p, where p is any of the prime factors of k.
Original entry on oeis.org
1, 2, 3, 3, 4, 5, 6, 4, 6, 6, 7, 7, 8, 9, 10, 5, 6, 9, 10, 8, 12, 10, 11, 9, 9, 11, 10, 12, 13, 14, 15, 6, 17, 8, 18, 12, 13, 14, 15, 10, 11, 17, 18, 13, 18, 15, 16, 11, 18, 12, 14, 14, 15, 14, 16, 15, 17, 17, 18, 18, 19, 20, 20, 7, 22, 23, 24, 10, 26, 24, 25, 15, 16, 17, 21, 18, 30, 20, 21, 12, 15, 14, 15, 22, 16, 24, 25, 16
Offset: 1
a(1): {1}, therefore a(1) = 1;
a(6): we have two alternative paths: {6, 4, 2, 1} or {6, 3, 2, 1}, with numbers [1, 2, 3, 4, 6] present, therefore a(6) = 5;
a(12): we have three alternative paths: {12, 8, 4, 2, 1}, {12, 6, 4, 2, 1} or {12, 6, 3, 2, 1}, with numbers [1, 2, 3, 4, 6, 8, 12] present, therefore a(12) = 7;
a(14): we have five alternative paths: {14, 12, 8, 4, 2, 1}, {14, 12, 6, 4, 2, 1}, {14, 12, 6, 3, 2, 1}, {14, 7, 6, 4, 2, 1} or {14, 7, 6, 3, 2, 1}, with numbers [1, 2, 3, 4, 6, 7, 8, 12, 14] present in at least one of the paths, therefore a(14) = 9.
-
a[n_] := Block[{lst = {{n}}}, While[lst[[-1]] != {1}, lst = Join[ lst, {Union[ Flatten[# - #/(First@# & /@ FactorInteger@#) & /@ lst[[-1]]]]}]]; Length@ Union@ Flatten@ lst]; Array[a, 75] (* Robert G. Wilson v, Apr 06 2020 *)
-
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);
A332809(n) = v332809[n];
-
from sympy import factorint
from functools import cache
@cache
def b(n): return {n}.union(*(b(n - n//p) for p in factorint(n)))
def a(n): return len(b(n))
print([a(n) for n in range(1, 89)]) # Michael S. Branicky, Aug 13 2022
A334230
Triangle read by rows: T(n,k) gives the meet of n and k in the graded lattice of the positive integers defined by covering relations "n covers (n - n/p)" for all divisors p of n.
Original entry on oeis.org
1, 1, 2, 1, 2, 3, 1, 2, 2, 4, 1, 2, 2, 4, 5, 1, 2, 3, 4, 4, 6, 1, 2, 3, 4, 4, 6, 7, 1, 2, 2, 4, 4, 4, 4, 8, 1, 2, 3, 4, 4, 6, 6, 4, 9, 1, 2, 2, 4, 5, 4, 4, 8, 4, 10, 1, 2, 2, 4, 5, 4, 4, 8, 4, 10, 11, 1, 2, 3, 4, 4, 6, 6, 8, 6, 8, 8, 12, 1, 2, 3, 4, 4, 6, 6, 8
Offset: 1
The interval [1,15] illustrates that, for example, T(12, 10) = 8, T(12, 4) = T(5, 6) = 4, T(8, 3) = 2, etc.
15
_/ \_
/ \
10 12
| \_ _/ |
| \ / |
5 8 6
\_ | _/|
\_|_/ |
4 3
| _/
|_/
2
|
|
1
Triangle begins:
n\k| 1 2 3 4 5 6 7 8 9 10 11 12 13 14
---+---------------------------------
1 | 1
2 | 1 2
3 | 1 2 3
4 | 1 2 2 4
5 | 1 2 2 4 5
6 | 1 2 3 4 4 6
7 | 1 2 3 4 4 6 7
8 | 1 2 2 4 4 4 4 8
9 | 1 2 3 4 4 6 6 4 9
10 | 1 2 2 4 5 4 4 8 4 10
11 | 1 2 2 4 5 4 4 8 4 10 11
12 | 1 2 3 4 4 6 6 8 6 8 8 12
13 | 1 2 3 4 4 6 6 8 6 8 8 12 13
14 | 1 2 3 4 4 6 7 8 6 8 8 12 12 14
-
\\ This just returns the largest (in a normal sense) number x from the intersection of the set of descendants of n and k:
up_to = 105;
buildWdescsets(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); (v); }
vdescsets = buildWdescsets(up_to);
A334230tr(n,k) = vecmax(setintersect(vdescsets[n],vdescsets[k]));
A334230list(up_to) = { my(v = vector(up_to), i=0); for(n=1,oo, for(k=1,n, i++; if(i > up_to, return(v)); v[i] = A334230tr(n,k))); (v); };
v334230 = A334230list(up_to);
A334230(n) = v334230[n]; \\ Antti Karttunen, Apr 19 2020
Showing 1-3 of 3 results.
Comments