[seqfan] The mapping k -> k + tau(k)

[hv at crypt.org]

Neil: you can skip to the 8 sequences at the end if you are short of time.
You may also want to modify A064491 to add crossreferences to some or all
of A165494 through to A165499.

In the following: tau(n) is the number of divisors of n; o(n) is the order
of n, the index of the greatest power of 2 dividing n.

1. The starting point was a(1) = 1; a(n+1) = a(n) + tau(a(n)), which turned
out to be A064491. The entry for this sequence includes a conjecture that
there exist constants c_1 and c_2 such that (asymptotically)
  c_1 ^ n < A064491(n) < c_2 ^ n

Considering this conjecture, the sequence appears to be dominated by runs
of order 0 values (which must reach a perfect square to escape) and order 1
(which need twice a square). The latter escape to order > 1, which must then
hit either a perfect square to go back to order 0, or a number of
the form px^2 (p prime) to go back to order 1.

2. Two sequences consider whether order 1 escape points next return to
order 0 or order 1. Letting f(x) = x + tau(x), these are defined as:
  b(n) := min(k: k > 0, o(f^k(2(2n-1)^2)) < 2)
  c(n) := f^b(n)(2(2n-1)^2)
That is: taking twice each odd square, iterate the map until the result
is no longer divisible by 4. Then b(n) is the number of iterations, and
c(n) the resulting value.

Here are the first 100 values:
b(n) = [ 
  2 3 3 3 2 3 7 2 3 6 2 9 3 2 10 3 2 2 5 7 3 4 7 10 5 5 10 8 2 7 3 8 7 4 9 36
  13 9 2 6 7 5 2 2 9 4 30 2 16 4 6 6 4 11 24 16 11 9 3 11 15 2 9 10 2 26 2 10
  3 3 4 13 11 5 12 3 7 17 21 17 17 12 5 4 3 8 19 9 2 5 3 2 2 2 3 7 12 19 29 3
]
c(n) = [
  7 38 71 122 178 265 415 486 602 799 927 1230 1321 1486 1810 1951 2214 2474
  2830 3194 3386 3738 4206 4639 4874 5358 5838 6222 6534 7101 7482 8145 8570
  9010 9722 10922 10922 11434 11882 12571 13274 13834 14474 15174 15962 16618
  17930 18074 19098 19674 20474 21354 22166 23162 24381 25058 25754 26606 27434
  28490 29599 30303 31370 32446 33354 35178 35402 36718 37582 38674 39918 41162
  42350 43322 44670 45626 46966 48458 49834 50962 52202 53474 54606 55914 57198
  58674 60430 61450 62694 64138 65553 67014 68474 69962 71550 73082 74774 76570
  78462 79226
]

Searching just for the odd values of c(n) shows more distinctly how they
become progressively rarer.
  d(n) := { k: o(c(k)) = 0 }
d(n) = [
  1 3 6 7 10 11 13 16 24 30
  32 40 55 61 62 91 115 129 139 190
  218 325 330 344 359 412 499 709 762 779
  791 1392 2230 2440 2947 3355 6008 6124 6718 6899
  7563 7872 8070 12529 15204 17582 19313 20706 28825 32188
  35382 36367 37521 40715 41292 50058 51381 53252 56784 64495
  65649 80494 81887 89598 100981 118711 120681 140282 157814 163654
  183255 239103 250416 266415 363435 376887 458077 490553 544600 698045
  804169 851082 859201 931864 959584 1221531 1439928 1538918 1644465 1736321
  1810785 1840067 2210516 2234873 2480582 2486323 2494442 2709068 2859150 2895974
]

3. Stumbling on the progression 60 -> 72 -> 84 -> 96 -> 108 -> 120 led me to
consider arithmetic progressions:
  e(n) := min(m: tau(m) = tau(m+k) = tau(m+2k) = ... = tau(m+(n-1)k) = k)
e(n) = [
  1 3 3 60 60 201 481 5989 3122037 4434429 13576837 183894465 187925171
  209072257
]
I conjecture that with the exception of 60, all other e(n) will be odd
and have tau(e(n)) a power of 2.

That led me further to consider what were the longest possible such progressions
for specific values of tau(k), and when they were reached:
  g(n) := max(k: exists m: tau(m) = tau(m+n) = ... = tau(m+(k-1)n) = n)
  h(n) := min(m: tau(m) = tau(m+n) = ... = tau(m+(g(n)-1)n) = n)

These are rather more problematic to calculate: lower bounds on g(n) can be
shown by example, but upper bounds must be proven, and h(n) cannot be defined
until g(n) is known.

g(n) = [
  1 3 1 8 1 *{4,13} 1 *{14,17} 1 *{3,8} 1 *{5,?} 1
]
h(n) = [
  1 3 4 5989 16 *12406475/4e9 64 *209072257/1e9 36 *8483478533/1e11
  1024 *60/1e9 4096
]

.. which is to say: for n=6, I have found progressions of 4 values (the first
at 12406475) searching up to 4e9; I have proven only that g(6) <= 13. I would
particularly welcome contributions to tighten the upper bounds.

4. Departing from the k+tau(k) theme, I considered also what might be the
maximum length arithmetic progression from n with all values having the same
tau(), if the difference could be chosen arbitrarily:
  j(n) := max(k: exists d: tau(n) = tau(n+d) = ... tau(n+(k-1)d))
  k(n) := min(d: tau(n) = tau(n+d) = ... tau(n+(j(n)-1)d))

We do have the constraint that j(n) <= n, and I suspect j(n) = n whenever
n is prime. (If so, the subset of k(n) for n prime might also be worth
a separate entry.)

j(n) = [ 1 2 3 2 5 3 7 4 2 5 11 ]
k(n) = [ * 1 2 5 6 2 150 19 16 12 1536160080 ]

Implicitly I require the difference to be a positive integer, but it seems
wrong to set k(1) = 1, so I choose to declare it undefined.

Hugo van der Sanden


%I A165494
%N A165494 Iterations of k -> k+tau(k) from 2(2n-1)^2 until result not divisible by 4
%S A165494 2,3,3,3,2,3,7,2,3,6,2,9,3,2,10,3,2,2,5,7,3,4,7,10,5,5,10,8,2,7,3,8,
%T A165494 7,4,9,36,13,9,2,6,7,5,2,2,9,4,30,2,16,4,6,6,4,11,24,16,11,9,3,11,15,
%U A165494 2,9,10,2,26,2,10,3,3,4,13,11,5,12,3,7,17,21,17,17,12,5,4,3,8,19,9,2
%Y A165494 A064491, A165495
%A A165494 Hugo van der Sanden (hv(AT)crypt.org)
%O A165494 1,1
%e A165494 For a(2) we start at 2.3^2=18; 18+tau(18)=24; 24+tau(24)=32; 32+tau(32)=38, which is not divisible by 4, so a(2)=3 for the 3 iterations needed.
%C A165494 This sequence and A165495 explore a critical aspect of the behaviour of A064491.
%K A165494 new,easy,nonn

%I A165495
%N A165495 First result not divisible by 4 when iterating k -> k+tau(k) from 2(2n-1)^2
%S A165495 7,38,71,122,178,265,415,486,602,799,927,1230,1321,1486,1810,1951,
%T A165495 2214,2474,2830,3194,3386,3738,4206,4639,4874,5358,5838,6222,6534,
%U A165495 7101,7482,8145,8570,9010,9722,10922,10922,11434,11882,12571,13274
%Y A165495 A064491, A165494, A165496
%A A165495 Hugo van der Sanden (hv(AT)crypt.org)
%O A165495 1,1
%e A165495 For a(2) we start at 2.3^2=18; 18+tau(18)=24; 24+tau(24)=32; 32+tau(32)=38, which is not divisible by 4, so a(2)=38.
%C A165495 This sequence and A165494 explore a critical aspect of the behaviour of A064491.
%K A165495 new,easy,nonn

%I A165496
%N A165496 Values k: A165495(k) is odd
%S A165496 1,3,6,7,10,11,13,16,24,30,32,40,55,61,62,91,115,129,139,190,218,325,
%T A165496 330,344,359,412,499,709,762,779,791,1392,2230,2440,2947,3355,6008,
%U A165496 6124,6718,6899,7563,7872,8070,12529,15204,17582,19313,20706,28825
%Y A165496 A064491, A165495
%A A165496 Hugo van der Sanden (hv(AT)crypt.org)
%O A165496 1,2
%C A165496 If A064491 reaches 2(2k-1)^2, it will then start a run of odd numbers if k is in this sequence.
%K A165496 new,easy,nonn

%I A165497
%N A165497 a(n) starts arithmetic progression of n terms separated by tau(a(n)), each term having the same number of divisors
%S A165497 1,3,3,60,60,201,481,5989,3122037,4434429,13576837,183894465,
%T A165497 187925171,209072257
%Y A165497 A064491, A165498, A165499
%A A165497 Hugo van der Sanden (hv(AT)crypt.org)
%O A165497 1,2
%e A165497 tau(60) = tau(72) = tau(84) = tau(96) = tau(108) = 12. This is the first such progression of length greater than 3, so a(4) and a(5) are both 60.
%C A165497 a(15) > 1e9
%K A165497 new,hard,nonn,more

%I A165498
%N A165498 Maximum length of arithmetic progression with difference n, such that each term k has tau(k) = n
%S A165498 1,3,1,8,1
%Y A165498 A064491, A165497, A165499, A165500
%A A165498 Hugo van der Sanden (hv(AT)crypt.org)
%O A165498 1,2
%e A165498 When tau(k) = 4, k cannot be divisible by 9 unless k = 27. An arithmetic progression of 9 terms with difference 4 must have a term divisible by 9, and k=27 is not part of a progression of 9 terms with tau(k)=4, so a(4) must be less than 9. Since a progression of 8 terms is achievable (eg starting at 5989), a(4) = 8 is proven.
%C A165498 a(n) = 1 for all odd n.
%C A165498 4 <= a(6) <= 13; 14 <= a(8) <= 17; 3 <= a(10) <= 8; 5 <= a(12).
%K A165498 new,hard,nonn,more

%I A165499
%N A165499 First term of maximal arithmetic progression with difference n, such that each term k has tau(k) = n
%S A165499 1,3,4,5989,16
%Y A165499 A064491, A165497, A165498, A165501
%A A165499 Hugo van der Sanden (hv(AT)crypt.org)
%O A165499 1,2
%e A165499 A165498(4) = 8, and exhaustive search finds tau(5989) = tau(5993) = tau(5997) = tau(6001) = tau(6005) = tau(6009) = tau(6013) = tau(6017) = 4 is the first example of an 8-term progression, so a(4) = 5989.
%C A165499 a(6) = 12406475 if A165498(6) = 4; if not, a(6) > 4e9.
%C A165499 a(8) = 209072257 if A165498(8) = 14; if not, a(8) > 1e9.
%C A165499 a(10) = 8483478533 if A165498(10) = 3; if not, a(10) > 1e11.
%C A165499 a(12) = 60 if A165498(12) = 5; if not, a(12) > 1e9.
%C A165499 A165498(n) = 1 for odd n, so a(7) = 64; a(9) = 36; a(11) = 1024; a(13) = 4096; a(15) = 144 etc.
%K A165499 new,hard,nonn,more

%I A165500
%N A165500 Maximum length of arithmetic progression starting at n such that each term k has tau(k)=tau(n)
%S A165500 1,2,3,2,5,3,7,4,2,5,11
%Y A165500 A165498, A165501
%A A165500 Hugo van der Sanden (hv(AT)crypt.org)
%O A165500 1,2
%e A165500 For n=4, tau(n)=3 so each term of the arithmetic progression must be a prime square. The difference d must be odd for n+d to qualify, in which case n+2d is even and does not qualify; so a(4)=2 is an upper bound.
%C A165500 Implicitly, we require the difference d of the arithmetic progression to be positive.
%C A165500 a(n) <= n for all n.
%K A165500 new,hard,nonn,more

%I A165501
%N A165501 Minimal common difference of maximal arithmetic progression starting at n such that each term k has tau(k)=tau(n)
%S A165501 1,2,5,6,2,150,19,16,12,1536160080
%Y A165501 A165499, A165500
%A A165501 Hugo van der Sanden (hv(AT)crypt.org)
%O A165501 2,1
%e A165501 For n=6, A165500(n)=3, and the least difference d such that tau(6) = tau(6+d) = tau(6+2d) is d=2, so a(6)=2.
%C A165501 a(1) is not well defined, since the maximal progression has only one term.
%K A165501 new,hard,nonn,more

__END__