A073934 -id:A073934 - cp's OEIS frontend

A333793 a(n) = A333794(n) - A073934(n).

0, 0, 0, 0, 0, 1, 1, 0, 1, 3, 3, 3, 3, 8, 5, 0, 0, 6, 6, 9, 12, 18, 18, 7, 9, 18, 6, 22, 22, 18, 18, 0, 30, 15, 24, 16, 16, 33, 28, 21, 21, 37, 37, 48, 24, 69, 69, 15, 37, 36, 29, 48, 48, 25, 54, 50, 49, 77, 77, 44, 44, 73, 49, 0, 56, 83, 83, 45, 113, 75, 75, 36, 36, 71, 54, 87, 87, 81, 81, 45, 25, 84, 84, 87, 57, 128, 119, 108, 108, 71

Offset: 1

Antti Karttunen, Apr 05 2020

nonn

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

Cf. A000079, A019434, A032742, A052126, A073934, A332904, A333123, A333794.

Partial sums of A333792.

A073934(n) = if(1==n,n,n + A073934(n-(n/vecmin(factor(n)[,1]))));
A333794(n) = if(1==n,n,n + A333794(n-(n/vecmax(factor(n)[, 1]))));
A333793(n) = (A333794(n)-A073934(n));

a(n) = A333794(n) - A073934(n).
a(p) = a(p-1), for all primes p.
a(A000079(n)) = a(A019434(n)) = 0, for all applicable n.

A333789 Numbers k for which A333790(k) < A073934(k).

Original entry on oeis.org

119, 143, 187, 209, 221, 238, 239, 286, 319, 357, 374, 407, 418, 419, 429, 442, 443, 451, 476, 478, 479, 561, 572, 595, 627, 638, 663, 667, 671, 703, 713, 714, 715, 717, 748, 779, 803, 814, 833, 836, 838, 839, 851, 858, 859, 884, 886, 887, 902, 935, 943, 952, 953, 956, 957, 958, 979, 989, 1001, 1045, 1067, 1071, 1073, 1105, 1111, 1122

Offset: 1

Antti Karttunen, Apr 12 2020

nonn

Numbers n for which the {smallest path sum when iterating from n to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k} cannot be obtained by always selecting the smallest prime factor of k (A020639). See the example in A333790 how that simple heuristic fails when starting from k=119.

Antti Karttunen, Table of n, a(n) for n = 1..36576; all terms <= 2^17

Cf. A020639, A060681, A073934, A333790.

Block[{a, b, nn = 1122}, a = Min@ Map[Total, #] & /@ Nest[Function[{a, n}, Append[a, Join @@ Table[Flatten@ Prepend[#, n] & /@ a[[n - n/p]], {p, FactorInteger[n][[All, 1]]}]]] @@ {#, Length@ # + 1} &, {{{1}}}, nn]; b = Array[If[# == 1, 1, Total@ NestWhileList[If[PrimeQ@ #, # - 1, # - #/FactorInteger[#][[1, 1]] ] &, #, # > 1 &]] &, nn]; Select[Range@ nn, a[[#]] < b[[#]] &]] (* Michael De Vlieger, Apr 15 2020 *)

search_up_to = 2^17;
A333790list(up_to) = { my(v=vector(up_to)); v[1] = 1; for(n=2, up_to, v[n] = n+vecmin(apply(p -> v[n-n/p], factor(n)[, 1]~))); (v); };
v333790 = A333790list(search_up_to);
A333790(n) = v333790[n];
A073934(n) = if(1==n,n,n + A073934(n-(n/vecmin(factor(n)[,1]))));
isA333789(n) = (A073934(n)!=A333790(n));

A332993 a(1) = 1, for n > 1, a(n) = n + a(A032742(n)).

Original entry on oeis.org

1, 3, 4, 7, 6, 10, 8, 15, 13, 16, 12, 22, 14, 22, 21, 31, 18, 31, 20, 36, 29, 34, 24, 46, 31, 40, 40, 50, 30, 51, 32, 63, 45, 52, 43, 67, 38, 58, 53, 76, 42, 71, 44, 78, 66, 70, 48, 94, 57, 81, 69, 92, 54, 94, 67, 106, 77, 88, 60, 111, 62, 94, 92, 127, 79, 111, 68, 120, 93, 113, 72, 139, 74, 112, 106, 134, 89, 131, 80, 156, 121

Offset: 1

Antti Karttunen, Apr 04 2020

nonn

Sum of those divisors of n that can be obtained by repeatedly taking the largest proper divisor (of previous such divisor, starting from n, which is included in the sum), up to and including the terminal 1.

			a(18) = 18 + 18/2 + 9/3 + 3/3 = 18 + 9 + 3 + 1 = 31.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A000203, A006022, A032742, A064097, A073934, A332994, A333783, A333791, A333794.

A332993(n) = if(1==n,n,n + A332993(n/vecmin(factor(n)[,1])));

a(1) = 1; and for n > 1, a(n) = n + a(A032742(n)).
a(n) = n + A006022(n).
a(n) = A332994(n) + A333791(n).
a(n) = A000203(n) - A333783(n).
It seems that for all n >= 1, a(n) <= A073934(n) <= A333794(n).

A333794 a(1) = 1, for n > 1, a(n) = n + a(n-A052126(n)).

Original entry on oeis.org

1, 3, 6, 7, 12, 13, 20, 15, 22, 25, 36, 27, 40, 41, 42, 31, 48, 45, 64, 51, 66, 73, 96, 55, 76, 81, 72, 83, 112, 85, 116, 63, 118, 97, 120, 91, 128, 129, 130, 103, 144, 133, 176, 147, 136, 193, 240, 111, 182, 153, 162, 163, 216, 145, 208, 167, 202, 225, 284, 171, 232, 233, 208, 127, 236, 237, 304, 195, 306, 241, 312, 183, 256, 257

Offset: 1

Antti Karttunen, Apr 05 2020

nonn

Conjecturally, also the largest path sum when iterating from n to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k.

			For n=119, the graph obtained is this:
              119
             _/\_
            /    \
          102    112
         _/|\_    | \_
       _/  |  \_  |   \_
      /    |    \ |     \
    51     68    96     56
    /|   _/ |   _/|   _/ |
   / | _/   | _/  | _/   |
  /  |/     |/    |/     |
(48) 34    64     48    28
     |\_    |    _/|   _/|
     |  \_  |  _/  | _/  |
     |    \_|_/    |/    |
    17     32     24    14
      \_    |    _/|   _/|
        \_  |  _/  | _/  |
          \_|_/    |/    |
           16      12    7
            |    _/|    _/
            |  _/  |  _/
            |_/    |_/
            8     _6
            |  __/ |
            |_/    |
            4      3
             \     /
              \_ _/
                2
                |
                1.
If we always subtract A052126(n) (i.e., n divided by its largest prime divisor), i.e., iterate with A171462 (starting from 119), we obtain 119-(119/17) = 112 -> 112-(112/7) -> 96-(96/3) -> 64-(64/2) -> 32-(32/2) -> 16-(16/2) -> 8-(8/2) -> 4-(4/2) -> 2-(2/2) -> 1, with sum 119+112+96+64+32+16+8+4+2+1 = 554, thus a(119) = 554. This happens also to be maximal sum of any path in above diagram.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Michael De Vlieger, Graph montage of k -> k - k/p, with prime p|k for 2 <= k <= 211, red line showing path of greatest sum, blue the path of least sum (cf. A333790), and purple where the two paths coincide, with other paths in gray.

Cf. A052126, A073934, A171462, A332994, A333790, A333793.

Array[Total@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, #, # > 1 &] &, 74] (* Michael De Vlieger, Apr 14 2020 *)

A333794(n) = if(1==n,n,n + A333794(n-(n/vecmax(factor(n)[, 1]))));

a(1) = 1; and for n > 1, a(n) = n + a(A171462(n)) = n + a(n-A052126(n)).
a(n) = A073934(n) + A333793(n).
a(n) = n + Max a(n - n/p), for p prime and dividing n. [Conjectured, holds at least up to n=2^24]
For all n >= 1, A333790(n) <= a(n) <= A332904(n).
For all n >= 1, a(n) >= A332993(n). [Apparently, have to check!]

A073933 Number of terms in n-th row of triangle in A073932.

Original entry on oeis.org

1, 2, 3, 3, 4, 4, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 7, 7, 8, 7, 8, 6, 8, 7, 8, 7, 8, 8, 8, 7, 8, 8, 9, 8, 8, 9, 10, 7, 9, 8, 8, 8, 9, 8, 9, 8, 9, 9, 10, 8, 9, 9, 9, 7, 9, 9, 10, 8, 10, 9, 10, 8, 9, 9, 9, 9, 10, 9, 10, 8, 9, 9, 10, 9, 9, 10, 10, 9, 10, 9, 10, 10, 10, 11, 10, 8

Offset: 1

Amarnath Murthy, Aug 19 2002

nonn

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

Cf. A032742, A060681, A073932, A073934, A073935.

One more than A064097.

a[1] := 1:for i from 2 to 500 do n := i:s := 1:while(n>1) do if isprime(n) then r := n-1: else r := n-n/ifactors(n)[2][1][1]; fi; n := r:s := s+1:od:a[i] := s:od:seq(a[k],k=1..500);

(define (A073933 n) (if (= 1 n) n (+ 1 (A073933 (A060681 n)))))
(define (A060681 n) (- n (A032742 n))) ;; See also code under A032742
;; Antti Karttunen, Aug 23 2017

From Antti Karttunen, Aug 23 2017: (Start)
a(1) = 1; for n > 1, a(n) = 1 + a(A060681(n)).
a(n) = 1 + A064097(n).
(End)

More terms from Sascha Kurz, Aug 23 2002

Offset corrected from 0 to 1 by Antti Karttunen, Aug 23 2017

A332904 Sum of distinct integers encountered on all possible paths from n to 1 when iterating with nondeterministic map k -> k - k/p, where p is any of the prime factors of k.

Original entry on oeis.org

1, 3, 6, 7, 12, 16, 23, 15, 25, 30, 41, 36, 49, 57, 66, 31, 48, 63, 82, 66, 105, 99, 122, 76, 91, 115, 90, 125, 154, 156, 187, 63, 222, 114, 240, 139, 176, 196, 217, 138, 179, 251, 294, 215, 264, 284, 331, 156, 300, 213, 258, 247, 300, 220, 345, 261, 334, 348, 407, 336, 397, 429, 395, 127, 492, 512, 579, 246, 650, 546, 617, 291, 364

Offset: 1

Antti Karttunen, Apr 04 2020

nonn

			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) = 1+2+3+4+6+8+12 = 36.
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}. These form a lattice illustrated below:
        15
       / \
      /   \
    10     12
    / \   / \
   /   \ /   \
  5     8     6
   \__  |  __/|
      \_|_/   |
        4     3
         \   /
          \ /
           2
           |
           1,
therefore a(15) = 1+2+3+4+5+6+8+10+12+15 = 66.

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

Cf. A064097, A073934, A332809, A332993, A332994, A333000, A333123.

Cf. A333790 (sum of the route with minimal sum), A333794.

Total /@ Nest[Function[{a, n}, Append[a, Union@ Flatten@ Table[Append[a[[n - n/p]], n], {p, FactorInteger[n][[All, 1]]}]]] @@ {#, Length@ # + 1} &, {{1}}, 72] (* Michael De Vlieger, Apr 15 2020 *)

up_to = 20000;
A332904list(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(vecsum,v); }
v332904 = A332904list(up_to);
A332904(n) = v332904[n];

For all primes p, a(p) = a(p-1) + p.

For all n >= 1, A333000(n) >= a(n) >= A333794(n) >= A333790(n).

A073935 Numbers n such that the n-th row of triangle in A073932 contains exactly the divisors of n.

Original entry on oeis.org

1, 2, 4, 6, 8, 16, 18, 20, 32, 42, 54, 64, 100, 128, 162, 256, 272, 294, 342, 486, 500, 512, 1024, 1458, 1806, 2048, 2058, 2500, 4096, 4374, 4624, 6498, 8192, 10100, 12500, 13122, 14406, 16384, 26406, 32768, 39366, 62500, 65536, 65792, 77658

Offset: 1

Amarnath Murthy, Aug 19 2002

nonn

John Machacek, Egyptian Fractions and Prime Power Divisors, arXiv:1706.01008 [math.NT], 2017.

Cf. A073932, A073933, A073934, A283423.

More terms from Sascha Kurz, Aug 23 2002

Name clarified by Sean A. Irvine, Dec 28 2024

A333790 Smallest path sum when iterating from n to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k.

Original entry on oeis.org

1, 3, 6, 7, 12, 12, 19, 15, 21, 22, 33, 24, 37, 33, 37, 31, 48, 39, 58, 42, 54, 55, 78, 48, 67, 63, 66, 61, 90, 67, 98, 63, 88, 82, 96, 75, 112, 96, 102, 82, 123, 96, 139, 99, 112, 124, 171, 96, 145, 117, 133, 115, 168, 120, 154, 117, 153, 148, 207, 127, 188, 160, 159, 127, 180, 154, 221, 150, 193, 166, 237, 147, 220, 186, 192, 172, 231

Offset: 1

Antti Karttunen, Apr 06 2020

nonn

Note that although in many cases a simple heuristics of always subtracting the largest proper divisor (i.e., iterating with A060681) gives the path with the minimal sum, this does not hold for the following numbers 119, 143, 187, 209, 221, ..., A333789, on which this sequence differs from A073934.

			For n=119, the graph obtained is this:
              119
             _/\_
            /    \
          102    112
         _/|\_    | \_
       _/  |  \_  |   \_
      /    |    \ |     \
    51     68    96     56
    /|   _/ |   _/|   _/ |
   / | _/   | _/  | _/   |
  /  |/     |/    |/     |
(48) 34    64     48    28
     |\_    |    _/|   _/|
     |  \_  |  _/  | _/  |
     |    \_|_/    |/    |
    17     32     24    14
      \_    |    _/|   _/|
        \_  |  _/  | _/  |
          \_|_/    |/    |
           16      12    7
            |    _/|    _/
            |  _/  |  _/
            |_/    |_/
            8     _6
            |  __/ |
            |_/    |
            4      3
             \     /
              \_ _/
                2
                |
                1.
By choosing the path that follows the right edge of the above diagram, we obtain the smallest sum for any such path that goes from 119 to 1, thus a(119) = 119+112+56+28+14+7+6+3+2+1 = 348.
Note that if we always subtracted the largest proper divisor (A032742), i.e., iterated with A060681 (starting from 119), we would obtain 119-(119/7) = 102 -> 102-(102/2) -> 51-(51/3) -> 34-(34/2) -> 17-(17/17) -> 16-(16/2) -> 8-(8/2) -> 4-(4/2) -> 2-(2/2) -> 1, with sum 119+102+51+34+17+16+8+4+2+1 = 354 = A073934(119), which is NOT minimal sum in this case.

Antti Karttunen, Table of n, a(n) for n = 1..20000
Michael De Vlieger, Graph montage of k -> k - k/p, with prime p|k for 2 <= k <= 121, red line showing path of least sum.

Cf. A032742, A060681, A332904, A333000, A333001, A333123, A333794.

Differs from A073934 for the first time at n=119, where a(119) = 348, while A073934(119) = 354. (See A333789).

Min@ Map[Total, #] & /@ Nest[Function[{a, n}, Append[a, Join @@ Table[Flatten@ Prepend[#, n] & /@ a[[n - n/p]], {p, FactorInteger[n][[All, 1]]}]]] @@ {#, Length@ # + 1} &, {{{1}}}, 76]   (* Michael De Vlieger, Apr 14 2020 *)

up_to = 65537; \\ 2^20;
A333790list(up_to) = { my(v=vector(up_to)); v[1] = 1; for(n=2, up_to, v[n] = n+vecmin(apply(p -> v[n-n/p], factor(n)[, 1]~))); (v); };
v333790 = A333790list(up_to);
A333790(n) = v333790[n];

a(n) = n + Min a(n - n/p), for p prime and dividing n.

For n >= 1, a(n) <= A333794(n) <= A332904(n), a(n) <= A333001(n).

A073932 Define f(n) = n - largest nontrivial divisor of n or f(n) = n-1 if n is a prime [that is, f(n) = A060681(n)]. Form a triangle in which the n-th row contains terms n, f(n), f(f(n)), ... until a 1 is reached; sequence gives triangle read by rows.

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 4, 2, 1, 5, 4, 2, 1, 6, 3, 2, 1, 7, 6, 3, 2, 1, 8, 4, 2, 1, 9, 6, 3, 2, 1, 10, 5, 4, 2, 1, 11, 10, 5, 4, 2, 1, 12, 6, 3, 2, 1, 13, 12, 6, 3, 2, 1, 14, 7, 6, 3, 2, 1, 15, 10, 5, 4, 2, 1, 16, 8, 4, 2, 1, 17, 16, 8, 4, 2, 1, 18, 9, 6, 3, 2, 1, 19, 18, 9, 6, 3, 2, 1, 20, 10, 5, 4, 2, 1

Offset: 1

Amarnath Murthy, Aug 19 2002

			Triangle begins:
   1;
   2, 1;
   3, 2, 1;
   4, 2, 1;
   5, 4, 2, 1;
   6, 3, 2, 1;
   7, 6, 3, 2, 1;
   8, 4, 2, 1;
   9, 6, 3, 2, 1;
  10, 5, 4, 2, 1;

Michael De Vlieger, Table of n, a(n) for n = 1..12386 (rows 1 <= n <= 1000, flattened)
John Machacek, Egyptian Fractions and Prime Power Divisors, Journal of Integer Sequences, Vol. 21 (2018), Article 18.3.7.

Cf. A032742, A060681, A073933, A073934, A073935.

j := 1:a[1] := 1:for i from 2 to 50 do n := i:j := j+1:a[j] := n:while(n>1) do if isprime(n) then r := n-1: else r := n-n/ifactors(n)[2][1][1]; fi; n := r:j := j+1:a[j] := n: od:od:seq(a[k],k=1..j);

Array[If[# == 1, {1}, NestWhileList[If[PrimeQ@ #, # - 1, # - #/FactorInteger[#][[1, 1]] ] &, #, # > 1 &]] &, 20] // Flatten  (* Michael De Vlieger, Apr 15 2020 *)

More terms from Sascha Kurz, Aug 23 2002

Offset corrected from 0 to 1 by Antti Karttunen, Aug 23 2017

A333792 a(1) = 0, then after the first differences of A333793.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, -1, 1, 2, 0, 0, 0, 5, -3, -5, 0, 6, 0, 3, 3, 6, 0, -11, 2, 9, -12, 16, 0, -4, 0, -18, 30, -15, 9, -8, 0, 17, -5, -7, 0, 16, 0, 11, -24, 45, 0, -54, 22, -1, -7, 19, 0, -23, 29, -4, -1, 28, 0, -33, 0, 29, -24, -49, 56, 27, 0, -38, 68, -38, 0, -39, 0, 35, -17, 33, 0, -6, 0, -36, -20, 59, 0, 3, -30, 71, -9, -11, 0, -37, 16

Offset: 1

Antti Karttunen, Apr 05 2020

sign

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A073934, A333793, A333794.

A333792(n) = if(1==n,0,A333793(n)-A333793(n-1)); \\ Other code as in A333793.

a(1) = 0; and for n > 1, a(n) = A333793(n) - A333793(n-1).

a(p) = 0 for all primes p. (May obtain zero values also on some nonprimes).

cp's OEIS Frontend

A333793 a(n) = A333794(n) - A073934(n).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A333789 Numbers k for which A333790(k) < A073934(k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A332993 a(1) = 1, for n > 1, a(n) = n + a(A032742(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A333794 a(1) = 1, for n > 1, a(n) = n + a(n-A052126(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A073933 Number of terms in n-th row of triangle in A073932.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Scheme

Formula

Extensions

A332904 Sum of distinct integers encountered on all possible paths from n to 1 when iterating with nondeterministic map k -> k - k/p, where p is any of the prime factors of k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A073935 Numbers n such that the n-th row of triangle in A073932 contains exactly the divisors of n.

Views

Author

Keywords

Links

Crossrefs

Extensions

A333790 Smallest path sum when iterating from n to 1 with nondeterministic map k -> k - k/p, where p is any prime factor of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs