The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 23
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,6 COMMENTS The iteration always terminates at 1, regardless of the prime factor chosen at each step. Although there may exist multiple paths to 1, their path lengths (A064097) are the same! See A064097 for a proof. Note that this behavior does not hold if we allow any divisor of k. First occurrence of k or 0 if no such value exists: 1, 6, 12, 24, 14, 96, 26, 85, 28, 21, 578, 30, 194, 38, 164, 39, 33, 104, 1538, 112, 35, 328, 58, 166, ..., . Records: 1, 2, 3, 5, 10, 12, 17, 21, 28, 33, 42, 47, 61, 103, 168, ..., . Record indices: 1, 6, 12, 14, 21, 30, 33, 35, 42, 62, 63, 66, 69, ..., . When viewed as a graded poset, the paths of the said graph are the chains of the corresponding poset. This poset is also a lattice (see Ewan Delanoy's answer to Peter Kagey's question at the Mathematics Stack Exchange link). - Antti Karttunen, May 09 2020 LINKS Antti Karttunen, Table of n, a(n) for n = 1..20000 Peter Kagey, Mathematics Stack Exchange, Does a graded poset on the positive integers generated from subtracting factors define a lattice? FORMULA a(n) = 1 iff n is a power of two (A000079) or a Fermat Prime (A019434). a(p) = a(p-1) if p is prime. a(n) = Sum_{p prime and dividing n} a(n - n/p) for any n > 1. - Rémy Sigrist, Mar 11 2020 EXAMPLE 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) MATHEMATICA 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]] PROG (PARI) 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 CROSSREFS Cf. A064097, A332809 (size of the lattice), A332810. Cf. A332904 (sum of distinct integers present in such a graph/lattice), A333000 (sum over all paths), A333001, A333785. Cf. A332992 (max. outdegree), A332999 (max. indegree), A334144 (max. rank level). Cf. A334230, A334231 (meet and join). Partial sums of A332903. Cf. also tables A334111, A334184. Sequence in context: A197081 A029395 A029282 * A289494 A029286 A286221 Adjacent sequences: A333120 A333121 A333122 * A333124 A333125 A333126 KEYWORD nonn,look AUTHOR Ali Sada and Robert G. Wilson v, Mar 09 2020 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 20 00:26 EDT 2024. Contains 371798 sequences. (Running on oeis4.)