Tau signature

Identifying numbers through successive tau values.

Sequences A309981 and A327265 are based on the problem of identifying numbers n through the values of tau(n+j) for a minimum number of j = 0, 1, 2, ..., k.

A309981(1, 2, ...) = (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, 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, ...)

The tau-signature

For any n >= 1 and k >= 0, we will call the (k+1)-component vector t(n,k) := (tau(n), tau(n+1), ..., tau(n+k)) a tau-signature.

The tau values tell us about the nature of n and its successors n+1, n+2, etc.: tau = 2 for primes, tau = 3 for squares of primes, tau = 4 for semiprimes and cubes of primes, etc. When the tau-signature is long enough, this will ultimately allow us to identify n, as we show below.

When k+1 is the shortest length such that this tau signature uniquely identifies n, i.e., no other n' has t(n',k) = t(n,k), then we will call this t(n,k) *the* tau signature of n and denote it by t(n).

Examples

A few very detailed examples

n = 1: Here we have tau(n) = 1, meaning that n has only 1 divisor. Since n = 1 is the only such number, t(n, k = 0) = (1) uniquely identifies n = 1, whence A309981(1) = k = 0. Moreover, this is the only 0 in the sequence, i.e., n = 1 is the only number that can be identified by it's sole number of divisors. Indeed, all n > 1 have tau(n) = d >= 2, and we have tau(p^(d-1)) = d for any prime p, so tau(n) = d, or t(n,0), does not identify n uniquely: we need at least one additional value tau(n+j), j = 1.

n = 2: Here tau(n) = 2 (as for any prime n: insufficient to identify n), but also tau(n+1) = 2, viz t(n, 1) = (2, 2). This means n and n+1 both are prime, and n = 2 is the only number with this property, i.e., with tau signature t(n, k = 1) = (2, 2). Hence A309981(2) = k = 1.

n = 3: Here tau(n) = 2 and tau(n+1) = 3, meaning that n is a prime such that n+1 is the square of a prime. Since all larger squares of primes are odd and therefore can't immediately follow a prime, this signature t(n, k = 1) = (2, 3) uniquely identifies n = 3, whence A309981(3) = 1.

n = 4: Here t(n, k = 1) = (3, 2), meaning that n is the square of a prime, followed by a prime. For all n = p^2 with prime p > 2, n+1 is an even composite, so n = 4 is the only number with this signature, and again, A309981(4) = 1.

n = 5: Here t(n, 1) = (2, 4). This is also the case for n = 5, 7, 13, 37, 61, ... thus insufficient to identify n. However, including the condition tau(n+2) = 2, viz t(n, 2) = (2, 4, 2), means that n, n+2 are primes separated by a semiprime (or prime cube p^3) n+1. But all larger twin primes are of the form 6m+-1, so the intermediate number is a larger multiple of 6 and has more than 4 divisors. Hence t(n, k = 2) = (2, 4, 2) identifies n = 5, so A309981(5) = 2.

n = 6: Here t(n, 2) = (4, 2, 4) means that n is a semiprime or p^3, followed by a prime n+1 = p', and then another semiprime or q^3. For prime powers, opposite parity of (n, n+1) = (p^3, p') would require p = 2 but then p' = 9 isn't prime, and (n+1, n+2) = (p', q^3) implies q = 2, p' = 7 which is our case n = 6. For any other solution one must have two semiprimes (n, n+2) = (2p, 2q), whence q = p+1, thus p = n = 2, not solution. So these 3 values uniquely identify n = 6, and again A309981(6) = 2.

n = 7: Here, t(n, 2) = (2, 4, 3), which means that n is prime, followed by a semiprime or cube of a prime, and then the square of a prime. But all prime cubes p^3 > 2^3 = 8 are odd and can't be followed by a prime squared, also odd. So we would need an even semiprime between prime n and n+2 = p^2. However, p^2 == 1 (mod 6) for all p > 3, so n+1 = 6m which is not a semiprime for m > 1. Thus, n = 7 is the only number with t(n, 2) = (2, 4, 3), and again A309981(7) = 2.

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).

Table of tau signatures

The comments use the fact that tau(n) = 2 <=> n is prime ; tau(n) = 3 <=> n = p^2 ; tau(n) = 4 <=> n = 2p > 4 or n = p^3 ; tau(n) = 5 <=> n = p^4 ; ...

  n  | tau signature (= tau(n+k), k=0... until unique) + PROOF (+ comment)
-----+-------------------------------
  1  | 1         only number with tau = 1 ; also only number with (unique) tau signature of length 1
  2  | 2, 2      only prime p s.th. p+1 is also prime (below, "p" always means a prime)
  3  | 2, 3      only p s.th. p+1 = (p')^2 (= square of a prime): consider the parity.
  4  | 3, 2      only p^2 followed by a prime p'
  5  | 2, 4, 2   only (lesser of twin prime pair) followed by 2*p' (or (p')^3): center of twins = 6*m
  6  | 4, 2, 4   only n = 2p (not p^3 because n+1 = p') s.th. n+2 = 2p'  (=> p' = p+1 => p=2, p'=3)
  7  | 2, 4, 3   only n = p s.th. p+1 = 2p' (not (p')^3 : odd as p) and p+2 = (p")² = 1 (mod 6) => 2p' = 6m
  8  | 4, 3      n+1 = (p')² = 1 (mod 6) if p' > 3, => n = 6m > 6: impossible for n = 2p or p^3. ∴ p' = 3.
  9  | 3, 4, 2
 10  | 4, 2, 6
 11  | 2, 6, 2, 4
 12  | 6, 2, 4
 13  | 2, 4, 4, 5
 14  | 4, 4, 5
 15  | 4, 5
 16  | 5, 2
 17  | 2, 6, 2, 6
 18  | 6, 2, 6    n+1 = p' > 3, {n,n+2} = {2p²,4p"}. One of p, p" must be 3.
 19  | 2, 6, 4, 4, 2
 20  | 6, 4, 4, 2, 8

Authorship

Created by User:M. F. Hasler, 5 April 2023

Additional proofs from Martin Fuller