This site is supported by donations to The OEIS Foundation.

User talk:Peter Luschny/StrongCoprimality

From OeisWiki
Jump to: navigation, search

Coprimorial of n / divisorial of n-1 provably always integer?

You say

Now, what is the ratio coprimorial / divisorial ? It turns out that we have to compare the coprimorial of n with the divisorial of n − 1 to get integer values.

Is coprimorial of n / divisorial of n-1 provably always integer? — Daniel Forgues 22:12, 4 August 2011 (UTC)

It seems obviously so, since a prime divisor of n − 1 is necessary prime to n, but the divisorial of n - 1 includes all divisors of n - 1, not just the prime divisors, which makes it less obvious... But then, the same thing could be said of a prime divisor of n + 1, necessary prime to n... Why is strong coprimality referring to n - 1 instead of n + 1, or either (very strong coprimality?)? — Daniel Forgues 22:55, 4 August 2011 (UTC)

The coproduct of n and m

DF: "Is coprimorial of n / divisorial of n-1 provably always integer?"

Yes. Assume not ...

DF: "Why is strong coprimality referring to n - 1 instead of n + 1,
or either (very strong coprimality?)?"

Not sure if we need "very strong coprimality". It's all here already,
and much more. To this end let us define the coproduct of n and m

cp := proc(n,m) local f; mul(f,f = coprimes(n) minus divisors(m)) end:

for n from 1 to 10 do seq(cp(n,m),m=1..11) od;

   1,   1,   1,  1,  1,   1,  1,  1,   1,  1,   1
   1,   1,   1,  1,  1,   1,  1,  1,   1,  1,   1
   2,   1,   2,  1,  2,   1,  2,  1,   2,  1,   2
   3,   3,   1,  3,  3,   1,  3,  3,   1,  3,   3
  24,  12,   8,  3, 24,   4, 24,  3,   8, 12,  24
   5,   5,   5,  5,  1,   5,  5,  5,   5,  1,   5
 720, 360, 240, 90,144,  20,720, 90, 240, 72, 720
 105, 105,  35,105, 21,  35, 15,105,  35, 21, 105
2240,1120,2240,280,448,1120,320, 35,2240,224,2240
 189, 189,  63,189,189,  63, 27,189,   7,189, 189

Here you see in the first column A001783

seq(cp(i,1),i=0..12);
1, 1, 1, 2, 3, 24, 5, 720, 105, 2240, 189, 3628800, 385

which is also the diagonal

seq(cp(i,i),i=0..12);
1, 1, 1, 2, 3, 24, 5, 720, 105, 2240, 189, 3628800, 385

Further the strong coprimality A181832 is the subdiagonal

seq(cp(i,i-1),i=0..12);
1, 1, 1, 1, 1, 3, 1, 20, 15, 35, 7, 36288, 35

compared to the cocoprimality

seq(cp(i-1,i),i=0..12);
1, 1, 1, 1, 1, 3, 4, 5, 90, 35, 224, 189, 25200

Now your proposal is the superdiagonal

seq(cp(i,i+1),i=0..12);
1, 1, 1, 1, 3, 4, 5, 90, 35, 224, 189, 25200 

And now for the "super strong coprimality" which is possessed by those
i with the property cp(i-1,i) = cp(i,i+1).

sscp := proc(n) if cp(i,i-1) = cp(i,i+1) then i else NULL fi end;
seq(sscp(i),i=0..399);  0, 1, 2, 3

Additionally the "super strong cocoprimality" which is possessed by
those i with the property cp(i-1,i) = cp(i+1,i).

cosscp := proc(n) if cp(i-1,i) = cp(i+1,i) then i else NULL fi end;
seq(cosscp(i),i=0..399); 0, 1, 2, 3

Now we only need a journal which will publish our result that the first
four numbers which are both super strong coprimes and super strong
cocoprimes are also the first self-inverse permutations of natural numbers
induced by reflections of the rooted plane trees and mountain ranges as
can be seen from A057164. Perhaps we should call these creatures coconuts? :) 

More seriously, perhaps the triangle for n from 1 to 10 do seq(cp(n,m),m=1..n)
is worth to be published on OEIS?

                                  1
                                 1, 1
                               2, 1, 2
                              3, 3, 1, 3
                           24, 12, 8, 3, 24
                           5, 5, 5, 5, 1, 5
                   720, 360, 240, 90, 144, 20, 720
                  105, 105, 35, 105, 21, 35, 15, 105
           2240, 1120, 2240, 280, 448, 1120, 320, 35, 2240
             189, 189, 63, 189, 189, 63, 27, 189, 7, 189

Peter Luschny 10:59, 5 August 2011 (UTC)

If we look at the same situation in terms of cardinality instead of products we find

numcp := proc(n,m) local f, coprimes;
coprimes := n -> select(k->igcd(k,n)=1,{$1..n}):
nops(coprimes(n) minus divisors(m)) end:
for n from 1 to 16 do seq(numcp(m,n),m=1..n) od;
                   0
                  0, 0
                0, 0, 1
               0, 0, 0, 1
             0, 0, 1, 1, 3
            0, 0, 0, 0, 1, 1
          0, 0, 1, 1, 3, 1, 5
         0, 0, 0, 1, 1, 1, 3, 3
       0, 0, 1, 0, 2, 1, 4, 2, 5
      0, 0, 0, 1, 2, 0, 3, 2, 3, 3
    0, 0, 1, 1, 3, 1, 5, 3, 5, 3, 9
   0, 0, 0, 0, 0, 1, 1, 2, 3, 2, 5, 3
 0, 0, 1, 1, 3, 1, 5, 3, 5, 3, 9, 3, 11
0, 0, 0, 1, 2, 1, 4, 2, 3, 2, 7, 2, 9, 5

for n from 1 to 16 do seq(numcp(n,n-m+1),m=1..n) od;

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

The three borders of the triangles which are equal are phi(n) - 1, A109606. Peter Luschny 12:34, 5 August 2011 (UTC)

Very strongly coprime to n

Very strongly coprime to n: numbers coprime to n but not divisors of n-1 or n+1

    {k coprime to n}             - {k | (n-1)}    - {k | (n+1)}
    ________________             _____________    _____________  

1:  {1}                          - {1}            - {1,2}          = {}
2:  {1}                          - {1}            - {1,3}          = {}
3:  {1,2}                        - {1,2}          - {1,2,4}        = {}
4:  {1,3}                        - {1,3}          - {1,5}          = {}
5:  {1,2,3,4}                    - {1,2,4}        - {1,2,3,6}      = {}
6:  {1,5}                        - {1,5}          - {1,7}          = {} 
7:  {1,2,3,4,5,6}                - {1,2,3,6}      - {1,2,4,8}      = {5}
8:  {1,3,5,7}                    - {1,7}          - {1,3,9}        = {5}
9:  {1,2,4,5,7,8}                - {1,2,4,8}      - {1,2,5,10}     = {7}
10: {1,3,7,9}                    - {1,3,9}        - {1,11}         = {7} 
11: {1,2,3,4,5,6,7,8,9,10}       - {1,2,5,10}     - {1,2,3,4,6,12} = {7,8,9} 
12: {1,5,7,11}                   - {1,11}         - {1,13}         = {5,7}
13: {1,2,3,4,5,6,7,8,9,10,11,12} - {1,2,3,4,6,12} - {1,2,7,14}     = {5,8,9,10,11}
14: {1,3,5,9,11,13}              - {1,13}         - {1,3,5,15}     = {9,11}
15: {1,2,4,7,8,11,13,14}         - {1,2,7,14}     - {1,2,4,8,16}   = {11,13} 
16: {1,3,5,7,9,11,13,15}         - {1,3,5,15}     - {1,17}         = {7,9,11,13}

Daniel Forgues 19:47, 5 August 2011 (UTC)

Left strongly coprime to n, right strongly coprime to n

Left strongly coprime to n: numbers coprime to n but not divisors of n-1

    {k coprime to n}             - {k | (n-1)}    
    ________________             _____________    

1:  {1}                          - {1}              = {}                                           
2:  {1}                          - {1}              = {}          
3:  {1,2}                        - {1,2}            = {}          
4:  {1,3}                        - {1,3}            = {}          
5:  {1,2,3,4}                    - {1,2,4}          = {3}        
6:  {1,5}                        - {1,5}            = {}            
7:  {1,2,3,4,5,6}                - {1,2,3,6}        = {4,5}        
8:  {1,3,5,7}                    - {1,7}            = {3,5}           
9:  {1,2,4,5,7,8}                - {1,2,4,8}        = {5,7}       
10: {1,3,7,9}                    - {1,3,9}          = {7}         
11: {1,2,3,4,5,6,7,8,9,10}       - {1,2,5,10}       = {3,4,6,7,8,9}    
12: {1,5,7,11}                   - {1,11}           = {5,7}        
13: {1,2,3,4,5,6,7,8,9,10,11,12} - {1,2,3,4,6,12}   = {5,7,8,9,10,11}
14: {1,3,5,9,11,13}              - {1,13}           = {3,5,9,11}         
15: {1,2,4,7,8,11,13,14}         - {1,2,7,14}       = {4,8,11,13}     
16: {1,3,5,7,9,11,13,15}         - {1,3,5,15}       = {7,9,11,13}

Right strongly coprime to n: numbers coprime to n but not divisors of n+1

    {k coprime to n}             - {k | (n+1)}
    ________________             _____________  

1:  {1}                          - {1,2}          = {}                  
2:  {1}                          - {1,3}          = {}
3:  {1,2}                        - {1,2,4}        = {}
4:  {1,3}                        - {1,5}          = {3}
5:  {1,2,3,4}                    - {1,2,3,6}      = {4}
6:  {1,5}                        - {1,7}          = {5} 
7:  {1,2,3,4,5,6}                - {1,2,4,8}      = {3,5,6}
8:  {1,3,5,7}                    - {1,3,9}        = {5,7}
9:  {1,2,4,5,7,8}                - {1,2,5,10}     = {4,7,8}
10: {1,3,7,9}                    - {1,11}         = {3,7,9} 
11: {1,2,3,4,5,6,7,8,9,10}       - {1,2,3,4,6,12} = {5,7,8,9,10} 
12: {1,5,7,11}                   - {1,13}         = {5,7,11}
13: {1,2,3,4,5,6,7,8,9,10,11,12} - {1,2,7,14}     = {3,4,5,6,8,9,10,11,12}
14: {1,3,5,9,11,13}              - {1,3,5,15}     = {9,11,13}
15: {1,2,4,7,8,11,13,14}         - {1,2,4,8,16}   = {7,11,13,14} 
16: {1,3,5,7,9,11,13,15}         - {1,17}         = {3,5,7,9,11,13,15}

Also on Talk:Strong coprimality.

Daniel Forgues 20:07, 5 August 2011 (UTC)

You say

And now for the "super strong coprimality" which is possessed by those i with the property cp(i-1,i) = cp(i,i+1).

but I think it should be

with the property cp(i,i-1) = cp(i,i+1).

which is not the same (the coproduct is not commutative, by its definition)...

Daniel Forgues 20:29, 5 August 2011 (UTC)

Actually, I don't think either that

And now for the "super strong coprimality" which is possessed by those

i with the property cp(i,i-1) = cp(i,i+1).

corresponds to the "very strongly coprime" as in my examples... — Daniel Forgues 20:41, 5 August 2011 (UTC)

The set of numbers which are very strongly coprime (or doubly strongly coprime) to would thus be the intersection of the set of numbers which are left strongly coprime to and the set of numbers which are right strongly coprime to . — Daniel Forgues 21:32, 5 August 2011 (UTC)

Re

Daniel, please take my words above with a pinch of salt. It is easy to generate new notions; however, only if these notions are backed by some hard propositions they have any value. By this I certainly do not mean that the above concepts are of no value. The discussion inspired me to submit A193805 which I hope will turn out to be useful. Peter Luschny 21:36, 5 August 2011 (UTC)

I'm also much into new notions or sequences which have (potential) mathematical value, I'm not so much into creating notions or sequences just for the sake of it. I don't know yet what is the value of left strongly coprime, right strongly coprime and very strongly coprime. Discussion to be continued on Talk:Strong coprimality... — Daniel Forgues 17:37, 6 August 2011 (UTC)