This site is supported by donations to The OEIS Foundation.

Talk:Tau signature

From OeisWiki
Jump to: navigation, search

PARI script to produce list of signatures

Code

Note: this may produce erroneous results due to limited search space. Only for checks, data not adequate for deducing OEIS sequences. 

find_dupe(s, n = 0, r = n+1, LIM = 10000 /*search limit*/)={
  for(j = r, LIM, for(k=1, #s, numdiv(j+k-1)==s[k] || next(2));
      /* signature found */   if( !n, n = j; next);
      if (j - n > RD, RD = j - n;
        printf("\nNew record distance: s=%d at n=%d and %d, dist.= %d\n", s, n, j, RD ));
      return(j)
  )/*return empty = not found*/}
 
sig = Map(); S = [] ; N = 100 ;  RD=1 /* record distance */
find_sig(n)= { for(L=1,99,
  my(s = apply(numdiv, [n..n+L-1])); /* look for this "signature" */
  setsearch(S, s) || find_dupe(s, n) || return(s))}
 
for(n=1, N, my(s = find_sig(n)); {
  if ( s, print(n": "s); S= setunion(S,[s]); mapput(sig, n, s);
        , print("No signature found for n = "n" !")
) )}

Results

1: [1]
2: [2, 2]
New record distance: s=[2] at n=3 and 5, dist.= 2
3: [2, 3]
New record distance: s=[3] at n=4 and 9, dist.= 5
4: [3, 2]
5: [2, 4, 2]
6: [4, 2, 4]
New record distance: s=[2,4] at n=7 and 13, dist.= 6
7: [2, 4, 3]
8: [4, 3]
New record distance: s=[3] at n=9 and 25, dist.= 16
9: [3, 4, 2]
10: [4, 2, 6]
11: [2, 6, 2, 4] * note: 2,6,2 also at 17
12: [6, 2, 4]
New record distance: s=[2,4] at n=13 and 37, dist.= 24
13: [2, 4, 4, 5]
14: [4, 4, 5]
15: [4, 5]
New record distance: s=[5] at n=16 and 81, dist.= 65
16: [5, 2]
17: [2, 6, 2, 6] * note: 2,6,2 also at 11
18: [6, 2, 6] ************
19: [2, 6, 4, 4, 2]
New record distance: s=[6,4,4,2] at n=20 and 716, dist.= 696
20: [6, 4, 4, 2, 8]
21: [4, 4, 2, 8]
22: [4, 2, 8]
23: [2, 8, 3]
24: [8, 3]
25: [3, 4, 4, 6, 2]
New record distance: s=[4,4,6,2] at n=26 and 1226, dist.= 1200
26: [4, 4, 6, 2, 8]
27: [4, 6, 2, 8, 2]

New record distance: s=[6,2,8,2] at n=28 and 6196, dist.= 6168
28: [6, 2, 8, 2, 6]
29: [2, 8, 2, 6, 4]
30: [8, 2, 6, 4, 4]
31: [2, 6, 4, 4, 4, 9]
32: [6, 4, 4, 4, 9]
33: [4, 4, 4, 9]
34: [4, 4, 9]
35: [4, 9]
36: [9, 2, 4]
New record distance: s=[2,4,4,8] at n=37 and 1381, dist.= 1344 /*from run with smaller LIMIT*/
37: [2, 4, 4, 8, 2]
38: [4, 4, 8, 2, 8]
39: [4, 8, 2, 8, 2]
40: [8, 2, 8, 2, 6]
41: [2, 8, 2, 6, 6]
42: [8, 2, 6, 6, 4]
43: [2, 6, 6, 4, 2]
New record distance: s=[6,6,4,2] at n=44 and 9836, dist.= 9792
44: [6, 6, 4, 2, 10]
45: [6, 4, 2, 10]
46: [4, 2, 10]
47: [2, 10, 3]
48: [10, 3]
New record distance: s=[3,6] at n=49 and 1681, dist.= 1632 /*from run with smaller LIMIT*/
49: [3, 6, 4]
50: [6, 4, 6, 2]
51: [4, 6, 2, 8]************OEIS says 6 : insufficient search space?
...

better PARI code

Code

Recall: t(n,k) := (tau(n+j), 0 <= j <= k). If t(n,k) = s = (s1,...,sN) then k = N+1. 

signatures = Map() /* Stored results:
   * integer n => [signature(n), search limit];
   * list sig  => [n, {n'}, {n"} search limit], where n, n' are the two earliest and 
                   n" is the latest known occurrence of sig. The first two allow to give 
                   m(n) = the smallest *distinct* occurrence in any case; n" allows to 
                   know from where on one has to start searching for further occurrences.
 /* if s = 0, find the signature of the integer n, unique within search limit LIMIT.
  * if s ≠ 0, return 0 if the signature s is not found elsewhere than at n, up to LIMIT
  *           otherwise return n' = latest known occurrence of s distinct from n
  */
signature(n, s = 0, LIMIT = 10^5) = {
  \\debug: printf("Calling sig(%d, %d)\n",n,s); if(20 < cnt+=1, error());
  if ( !s \\ search the signature  of n
  ,    s = iferr( mapget(signatures, n), E, []); \\ check if already known
       #s || \\ never searched for: store & append elements until unique
          while ( signature(n, s = concat(s, numdiv(n+#s)), LIMIT), )
          \\ while this s is found somewhere else, append more elements to s
          \\ otherwise it's the (conjectural...) signature of n:
          || [mapput(signatures, n, [s, LIMIT]), return(s)];
       \\ a signature is already known for n: check if OK
       s[2] >= LIMIT && return(s[1]);
       \\ We must push the search further. (Find out where we have to start the search...?)
       \\ Check whether s is found somewhere later.
       s = s[1]; while( s = signature(n, s = concat(s, numdiv(n+#s)), LIMIT), );
             \\ (Note: this [first] call to signature() ensures we search up to LIMIT,
             \\  which is was not the case for the result stored in the Map() before.)
       mapput(signatures, n, [s, LIMIT]); return(s)
  );
  \\ Search for (pseudo)signature s, given that it does occur at n.
  \\ Return 0 if it doesn't occur elsewhere up to LIMIT, else the LEAST known *distinct* n'
  \\ NOTE: we can't be sure that this is called with increasing n (for a given s) !
  my(r = iferr(mapget(signatures, s), E, [n,n])); \\ initialize to [n] if not yet there
  r[#r] < n && mapput(signatures, s, r = if ( #r>2, [r[1],r[2],n,n], [r[1],n,n] )); \\ complete or update largest known.
  r[1] < n && return(r[1]); \\ that's all we need
  r[2] > n && (#r > 2 || r[2] >= LIMIT) && return(if(#r>2, r[2], 0)); \\ idem (if r[2] = LIMIT, r[1] = n is the only instance)
  #s > n\/3 && [mapput(signatures, s, [n,oo]), return(0)]; \\ n=1 => [1], {2,3,4}=>[x,y], {5,6,7}=>[x,y,z]
  #r > 2 && error([n,r,LIMIT]); \\ should not happen: if #r > 2 we know n' ≠ n with the same s.
  for ( j = 1, LIMIT, \\ start over at j=1: if the function was called with a large n, we're not sure r[1] is the smallest possible.
    for ( k = 1, #s, numdiv(j+k-1) != s[k] && next(2)); j==n && next;
    mapput(signatures, s, [r[1], j, j]); return(j) \\ searched only up to j
  )/*end for j*/;
  mapput(signatures, s, [r[1], n, LIMIT]) \\ no other occurrence up to LIMIT
}

for(n=1, 100, print("t("n") = ",s=signature(n),"\t m("n") = ",if(n>1,signature(n,s[^-1]),"-")))

Result

 
t(1) = [1]       m(1) = -
t(2) = [2, 2]    m(2) = 3
t(3) = [2, 3]    m(3) = 2
t(4) = [3, 2]    m(4) = 9
t(5) = [2, 4, 2]         m(5) = 7
t(6) = [4, 2, 4]         m(6) = 10
t(7) = [2, 4, 3]         m(7) = 5
t(8) = [4, 3]    m(8) = 6
t(9) = [3, 4, 2]         m(9) = 25
t(10) = [4, 2, 6]        m(10) = 6
t(11) = [2, 6, 2, 4]     m(11) = 17
t(12) = [6, 2, 4]        m(12) = 18
t(13) = [2, 4, 4, 5]     m(13) = 37
t(14) = [4, 4, 5]        m(14) = 21
t(15) = [4, 5]   m(15) = 6
t(16) = [5, 2]   m(16) = 81
t(17) = [2, 6, 2, 6]     m(17) = 11
t(18) = [6, 2, 6]        m(18) = 12
t(19) = [2, 6, 4, 4, 2]  m(19) = 31
t(20) = [6, 4, 4, 2, 8]  m(20) = 716
t(21) = [4, 4, 2, 8]     m(21) = 57
t(22) = [4, 2, 8]        m(22) = 6
t(23) = [2, 8, 3]        m(23) = 29
t(24) = [8, 3]   m(24) = 30
t(25) = [3, 4, 4, 6, 2]  m(25) = 121
t(26) = [4, 4, 6, 2, 8]  m(26) = 1226
t(27) = [4, 6, 2, 8, 2]  m(27) = 51
t(28) = [6, 2, 8, 2, 6]  m(28) = 6196
t(29) = [2, 8, 2, 6, 4]  m(29) = 41
t(30) = [8, 2, 6, 4, 4]  m(30) = 66
t(31) = [2, 6, 4, 4, 4, 9]       m(31) = 211
t(32) = [6, 4, 4, 4, 9]  m(32) = 92
t(33) = [4, 4, 4, 9]     m(33) = 85
t(34) = [4, 4, 9]        m(34) = 14
t(35) = [4, 9]   m(35) = 6
t(36) = [9, 2, 4]        m(36) = 100
t(37) = [2, 4, 4, 8, 2]  m(37) = 1381
t(38) = [4, 4, 8, 2, 8]  m(38) = 86
t(39) = [4, 8, 2, 8, 2]  m(39) = 1191
t(40) = [8, 2, 8, 2, 6]  m(40) = 136
t(41) = [2, 8, 2, 6, 6]  m(41) = 29
t(42) = [8, 2, 6, 6, 4]  m(42) = 906
t(43) = [2, 6, 6, 4, 2]  m(43) = 331
t(44) = [6, 6, 4, 2, 10]         m(44) = 9836
t(45) = [6, 4, 2, 10]    m(45) = 261
t(46) = [4, 2, 10]       m(46) = 6
t(47) = [2, 10, 3]       m(47) = 79
t(48) = [10, 3]  m(48) = 80
t(49) = [3, 6, 4]        m(49) = 1681
t(50) = [6, 4, 6, 2]     m(50) = 722
t(51) = [4, 6, 2, 8, 4, 8]       m(51) = 22611
...

A361088 : table of tau signatures

I tentatively propose that sequence, I hope it will be accepted.

m(n)

I was able to adapt some existing code to calculate m(n) as defined in a309981.txt fairly efficiently; however my results do not fully agree with those of User:Jon E. Schoenfield, so I have emailed him with a request to help resolve the discrepancy.

To my mind, establishing a particular value of A309981(n)=k involves both a proof that t(n,k) is unique and a proof by counterexample that t(n,k-1) is not unique. I intend therefore to propose m(n) as a new sequence to serve as a reference set of such counterexamples, once the discrepancy with Jon Schoenfield's results has been resolved. Hugo van der Sanden (talk) 08:24, 8 April 2023 (EDT)

I agree, I have already 2 days ago submitted a comment that I find, e.g., m(40) = 136 instead of the very large number given there. NJAS has withheld the comment from publication and wants to wait for an answer by Jon S. I had previously written to Jon S. but learned only today that he was busy due to a private problem and therefore hadn't dealt with his mails in recent days. I also planned to add the column m(n) e.g. in the examples section of the sequence; and I think we should also have the table giving the signatures t(n), I submitted that as https://oeis.org/draft/A361088. — MFH 21:07, 8 April 2023 (EDT)
PS: specifically, with the above ("better") PARI program, if you type
gp > signature(40)
 %3 = [8, 2, 8, 2, 6]
gp > signature(40, %[^-1]) \\ or use: mapget(signatures, %[^-1])
 %4 = 136

A309981(49)

This seems to be the first case that relies on a Pell equation. Can someone clarify how we prove that A309981(49) = 2? Trying out the first few prime solutions to the Pell equation x^2 + 1 = 2y^2 suggests that perhaps it is guaranteed that x^2 + 2 is always divisible by 51 in those cases (which would be sufficient for a proof), but I do not know if that is true and provable. Hugo van der Sanden (talk) 14:12, 9 April 2023 (EDT)

I note that the main page shows this:
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).
.. but this seems to fall short of a proof - it talks about "known values" (ie solutions of p^2 + 1 = 2q^2 for prime p, q), but does not rule out the possibility that other values exist. For the record, the next two solutions look to be (63018038201, 44560482149) and (19175002942688032928599, 13558774610046711780701) with no other solutions at least for p < 10^27, and p^2 + 2 factorizes for those two cases as 3^2 11 17 19 59 601 2281 1535466241 and 3 17 233 241 1153 5521 127497803 89120964299 1774998973441. Hugo van der Sanden (talk) 12:18, 10 April 2023 (EDT)
I investigated the possibility that the modular structure of solutions to the Pell equation would yield a proof, but it looks unlikely that it will do so. Let (x_0, y_0) = (1, 1), and let (x_{i+1}, y_{i+1}) = (3x_i+4y_i, 2x_i+3y_i) be the solutions of the Pell equation x^2+1=2y^2. Then it appears that modulo any given prime p>3, if (x_i, y_i) are periodic with an odd period 2t+1 then either x_i or y_i is divisible by p precisely when i == t (mod 2t+1), and x_i^2+2 never is; conversely if it has an even period 2t, then x_i^2+2 is divisible by p precisely when i == t-1 or i == t (mod 2t), and x_i, y_i never are. If this pattern holds for all p, then it will not be possible to rule out a further solution with (x_i, y_i, (x_i^2+2)/3) all prime by modular coverage alone. Hugo van der Sanden (talk) 20:33, 13 April 2023 (EDT)
Yes, I also tried a modular approach, without conclusive result so far, but I still think that might be the way to go, also in the general case and for "automated" proofs. (I admit I didn't tried very hard/long so far -- to do ASAP...) — MFH 09:53, 18 April 2023 (EDT)

Automation

I have extended code originally written for A165500/1, and it is looking stable and giving quite good results so far: it has so far established for itself values of A309981 and found the least counterexample for each shorter signature for 89 values of n in (1 <= n <= 100), and (83, 73, 24) of subsequent batches of 100; the 11 values up to n=100 that it has not yet established are (33, 34, 35, 49, 50, 64, 95, 96, 97, 98, 99), and I have ideas to extend it further at least another 5 of those. (For anyone interested in looking at Perl code, the A309981-specific parts are in the Type::Track module, but they are part of a wider ecosystem. The primary top-level programs are gtauseq and harness).

The approach is based on applying (optionally bounded) modular constraints, along with a semi-intelligent run harness that decides which entry to tackle next based on a bunch of manually-tweaked heuristics. It searches for constraints for each modulus up to a set limit (again decided by the run harness's heuristics), and for a given modulus m applies the following constraints for any target value v (as implemented by the "apply_m" function):

  • if tau(v) < tau(m), then v cannot be == 0 (mod m);
  • if tau(v) = tau(m), then v cannot be == 0 (mod m) for v > m;
  • when exists k: m = k rad(k), if tau(k) does not divide tau(v), then v cannot be == hk (mod m) for any h: gcd(h, k) = 1;
  • if tau(v) is odd, then v cannot be == q (mod m) for any quadratic non-residue q (mod m).

Additionally if any value is forced to be a product of the form v = xy^{2z}, with x, z known, it rewrites the current set of constraints in terms of y instead of v, and iterates over that instead. (This is referred to in the code as "fixing a power".)

The further extensions planned are as follows.

  • To leverage the fixed-power code also to detect when xy^{2z}-xi^2 is a target under consideration for some i, and apply further constraints based on the x(y^z-i)(y^z+i) factorization. That should at least allow it to establish 33-35.
  • Similar logic based on factorization of y^{2z} + 1, which should allow it to establish 64.
  • Based on to-be-determined criteria, to shard the tests over some modulus. For t(50, 4) for example, it already knows that any counterexample must have v == 26 (mod 30). If I ask it to consider only v == 0 (mod 4) it fixes the square at v+2 and determines that the case is not possible; if I ask it to consider only v == 2 (mod 4) it fixes the square at v and also determines that the case is not possible. But it will be a fair bit of new code to a) decide and implement the criteria, b) apply that sharding automatically, and c) detect and make use of the results.

Any suggestions for further improvement (or requests for better explanation) are welcome. I'd particularly like to generate a readable proof based on the findings of this code, but I have no clue how to do that right now. Hugo van der Sanden (talk) 14:46, 10 April 2023 (EDT)

I've implemented the first of those extensions, at least in a crude form, and got a fair bit further: I have now established 593 values for 1 <= n <= 1000, including all but 19 for 1 <= n <= 300. Counterexamples for k > 11 are proving harder to find for the Perl implementation, so I plan to see next if I can adapt my C implementation (developed primarily for A292580), and return to the other Perl extensions later.
Missing values for n <= 300 are in the table below. Hugo van der Sanden (talk) 10:57, 12 April 2023 (EDT)
I implemented the second of the extensions, and handled 64 as an exception rather than implementing the third. I've updated the table to show remaining missing values up to 350; in full it has now found all but 59 values up to n=600 and all but 293 up to n=1000. Hugo van der Sanden (talk) 12:12, 16 April 2023 (EDT)
I'm not sure I understand. Is max the maximum length the tau-signature may have? E.g., at n = 242 you have a counter-example t(n, min-1) = t(m, min-1) := tau(m, 0 <= j < min), with min = 8 and m = 65...322, right? (For n=49 we do have t(49, 2-1) = (tau(49), tau(50)) = (3, 6) = t(1681, 2-1), but t(49, 2) = (3, 6, 4) != t(1681, 2) = (3, 6, 12): here we know the length of the true tau-signature must be > 2, but <= max = 4, right?) So we know that the tau-signature of n = 242 must have length > 8, at least 9. Now maybe I misunderstood that, but if "max" is the upper limit for the length of the signature, then 8 < length <= 9, so length = 9, i.e., t(242) = t(242, 9-1)? Then this wouldn't be an undetermined case any more... So, maybe "max" is not the upper limit? — MFH 23:07, 18 April 2023 (EDT)
'min' and 'max' are the range of possible values for A309981(n): everything below 'min' is ruled out by counterexample; everything above 'max' is ruled out by the type of modular constraint described above. Re-reading the definition, I see that "t(n,k)" should be a (k+1)-element vector (not k-element as I had thought), so the 6th column should be called "t(n,max-1)". Does that fix the confusion?
For me, it would make life simpler (i.e. less prone to error) if t(n,k) were redefined to be a k-element vector; I find myself struggling to parse your comments about 49 and 242 because of the cognitive dissonance, but I'll have another go after more coffee. Hugo van der Sanden (talk) 07:30, 19 April 2023 (EDT)

Authorship

The "Authorship" section is not needed, given that the edit history lists all authors and even allows to trace who added any particular part of the text. --Andrey Zabolotskiy (talk) 08:23, 11 April 2023 (EDT)

I see your point; however I can also imagine it being a fair bit of effort to recover the information from the history when using this data to create or augment OEIS sequences, so I think there remains some value in keeping the section. Hugo van der Sanden (talk) 10:17, 11 April 2023 (EDT)
I also agree that it wouldn't be needed, for the same reason as signatures wouldn't be needed in the main OEIS given that one can (and should) consider the editing history to know (precisely) who wrote what (often comes with surprises). However, Style_Sheet_for_OEIS_Wiki asks to put this section at the end of the page. That's the only reason I put it, not because I want to see my name, so if that policy is obsolete, I don't object at all to delete it. — MFH 13:05, 11 April 2023 (EDT)

Name of the page

I think the current title is not the best choice. I think "tau signature" (which unfortunately will become capitalized, but "The tau signature" is not the conventional style for wikimedia pages) or "τ-signature" (with "tau signature" redirecting there) or maybe "A361088" (still only proposed) or "A361088: tau signature" would be better. — MFH 13:10, 11 April 2023 (EDT)

+1 for either "tau signature" or "τ-signature". Hugo van der Sanden (talk) 14:03, 11 April 2023 (EDT)
You can make the title be displayed as "tau signature" (with first letter in lower case) by moving it to "Tau signature" and inserting {{DISPLAYTITLE:tau signature}} in the wiki source. /Pontus von Brömssen (talk) 11:11, 12 April 2023 (EDT)
OK, thanks for that hint! I will definitely try that. What is would be your personal preference for the displayed title: " 
τ
-signature" or "tau signature"? — MFH 20:22, 13 April 2023 (EDT)
Retrieved from "https://oeis.org/w/index.php?title=Talk:Tau_signature&oldid=1654162"