cp's OEIS Frontend

A309981 a(n) is the smallest number k such that the value of n can be deduced given only the values tau(n), tau(n+1), ..., tau(n+k), where tau is the number of divisors function.

%I A309981 #29 Apr 25 2023 01:04:13
%S A309981 0,1,1,1,2,2,2,1,2,2,3,2,3,2,1,1,3,2,4,4,3,2,2,1,4,4,4,4,4,4,5,4,3,2,
%T A309981 1,2,4,4,4,4,4,4,4,4,3,2,2,1,2,3,6,6,6,6,5,4,4,4,5,4,3,2,1,1,6,6,5,5,
%U A309981 6,5,5,4,6,6,6,5,4,3,2,1,2,6,6,6,5,4,6
%N A309981 a(n) is the smallest number k such that the value of n can be deduced given only the values tau(n), tau(n+1), ..., tau(n+k), where tau is the number of divisors function.
%C A309981 For every number n in 2..87, there exists at least one other number m in 2..72970801 such that tau(m+j) = tau(n+j) for each nonnegative j less than the listed term, which establishes a lower bound for the term. (For the smallest such m corresponding to each term in the Data, see the Links.) That each value listed in the Data is the exact value was proved using a variety of methods such as those in the Example section and some of the methods in the _R. J. Mathar_ link at A161460.
%C A309981 From _Jon E. Schoenfield_, Sep 23 2019: (Start)
%C A309981 It follows from the definition of this sequence that a(n) >= a(n-1) - 1, which provides an easy lower bound on a(n) (given a(n-1)). An easy (but weak) upper bound is provided by a(n) <= (ceiling(sqrt(n))+1)^2 - n, since any counterexample would mean that there exists a number n for which a list of the tau values of all the consecutive integers from n through (ceiling(sqrt(n))+1)^2 would not be sufficient to allow the deduction of the identity of n, even though those consecutive integers would include at least two consecutive squares (immediately identifiable as squares by their odd tau values), and the only pair of consecutive squares with difference d is (floor(d/2)^2, ceiling(d/2)^2).
%C A309981 For the indices at which the values 0..17 first appear in this sequence, see A327265.
%C A309981 Do all nonnegative integers eventually appear? (End)
%H A309981 Jon E. Schoenfield, <a href="/A309981/a309981_1.txt">Table of n, m(n) for n = 1..87, where m(n) is the smallest nonnegative integer (other than n) such that tau(m+j) = tau(n+j) for all j in 0..a(n)-1</a> (corrected Apr 20 2023, with thanks to M. F. Hasler for pointing out that there were errors in the original file).
%F A309981 a(1)=0; for n > 1, a(n) = 1 iff n is a term of A161460.
%e A309981 a(1) = 0 is the only occurrence of 0 since n = 1 is the only number that has only 1 divisor and therefore tau(n) = 1 uniquely identifies n = 1. For any other number we need more tau values (tau(n+j), 0 <= j <= k) in order to identify n through these k+1 values.
%e A309981 a(2) = 1: n = 2 is the only prime such that n+1 is also prime, therefore tau(n) = 2 and tau(n+1) = 2 implies n = 2 (and only tau(n) = 2 is not enough).
%e A309981 a(3) = 1: n = 3 is the only prime such that n+1 is the square of a prime, i.e., n+1 has 3 divisors, so tau(n) = 2 and tau(n+1) = 3 uniquely identify n = 3.
%e A309981 a(4) = 1: n = 4 is the only square of a prime such that n+1 is a prime. (For all other n = p^2 with p prime, n+1 is an even composite.)
%e A309981 a(5) = 2: the numbers tau(n) and tau(n+1) are 2 and 4, respectively, for n = 5, 7, 13, 37, 61, ..., but 5 is the only number n such that (tau(n), tau(n+1), tau(n+2)) = (2, 4, 2). (Indeed this means that n, n+2 are twin primes, separated by a semiprime n+1. But all larger twin primes are of the form 6m+-1, so the intermediate number is a larger multiple of 6 with more than 4 divisors.)
%e A309981 From _M. F. Hasler_, Mar 31 2023: (Start)
%e A309981 a(6) = 2: Here tau(n) = 4, tau(n+1) = 2, tau(n+2) = 4 mean that n is a semiprime or p^3, followed by a prime and then another semiprime or q^3. For larger n, prime powers are excluded through parity ((n, n+1) = (p^3, p') and/or (n+1, n+2) = (p', q^3) are all odd), and one can't have two even semiprimes separated by 2, n = 2p, n+2 = 2q. So n = 6 is the only such number. (End)
%e A309981 a(49) = 2: (tau(n), tau(n+1)) = (3,6) for n = 49, 1681, and only two other known values (i.e., for squares of terms > 3 in A086397), but (tau(n), tau(n+1), tau(n+2)) = (3, 6, 4) only for n = 49 (which is the only square of a prime p such that both sqrt((p^2 + 1)/2) and (p^2 + 2)/3 are also prime).
%Y A309981 Cf. A000005, A086397, A161460, A327265.
%K A309981 nonn
%O A309981 1,5
%A A309981 _Jon E. Schoenfield_, Aug 25 2019