Friday, August 26, 2016

The abc-conjecture 1

Suppose a, b and c are natural numbers such that a,b,c are mutual co-prime and a+b=c. Those triples are called abc-triplets. The abc-conjecture concern the unusual possibility that

(1) a+b>rad(ab(a+b))

where rad is the radical, the product of all unique prime factors of a number. I.e. rad(4)=2, rad(6)=6, rad(60)=30, rad(81)=3, rad(101)=101, ...

There is an infinite number of pairs (a,b) as (1), but given a real number epsilon>0 there seems to be only a finite number of abc-triplets (a,b,a+b) such that

(2) a+b>rad(ab(a+b))^(1+epsilon) 

and that's one version of the famous abc-conjecture.

: abcpair \ a b -- flag
  locals| b a |
  a b ugcd 1 =
  a b + 
  dup a ugcd 1 =
  swap b ugcd 1 =
  and and ;

test if (a,b,a+b) is a abc-triplet, and

: unusual \ a b -- flag
  locals| b a |
  a b 2dup + * * radical
  a b + < ;

test if a+b>rad(ab(a+b)).

1 1000 condition non create-set zdup cardinality . 999  ok

creates the set {1,...,999}.

zdup cartprod zdup cardinality . 998001  ok

create the Cartesian product {1,...,999}x{1,...,999} and 

2dim < filter-set zdup cardinality . 498501  ok

filter the set so that the first component is less than the second.

2dim abcpair filter-set zdup cardinality . 303791  ok

This skip all (a,b) but those where (a,b,a+b) is a abc-triplet.

2dim unusual filter-set zdup cardinality . 32  ok

This is the remaining set of pairs such that (1):

zdup cr zet.
{(1,8),(1,48),(1,63),(1,80),(1,224),(1,242),(1,288),(1,512),(1,624),(1,675),(1,728),(1,960),(2,243),(3,125),(4,121),(5,27),(5,507),(7,243),(13,243),(25,704),(27,512),(32,49),(32,343),(49,576),(81,175),(81,544),(100,243),(104,625),(169,343),(200,529),(343,625),(640,729)} ok

Considering the pairs as Gaussian integers and transform the set of unusual pairs to their Gaussian norms give:

zdup 2dim gnorm transform-set zdup cardinality . cr zet. 32
{65,754,2305,3425,3970,6401,14657,15634,37186,50177,58565,59053,59098,59218,69049,82945,118673,146210,257074,262145,262873,302497,319841,334177,389377,401441,455626,496241,508274,529985,921601,941041} ok

Since the both sets have 32 elements I hasten to raise the conjecture:

(3) All (ordered) unusual pairs has unique Gaussian norms. 

To test the conjecture for different limits without stack overflow, conj3 works:

: abcunusual \ ab -- flag
  2dup abcpair 0= 
  if 2drop false
  else unusual
  then ;

: conj3 \ n -- set flag
  true locals| flag |
  0 >zst \ empty set on zst stack
  2 
  ?do i 1 
     ?do i j abcunusual 
        if i j gnorm dup zdup smember
           if false to flag drop i j pad 2! leave
           else >zst zfence union
           then
        then
     loop flag 0= if leave then
  loop flag ;

100 conj3 . -1  ok

zet. {65,754,2305,3425,3970,6401} ok

5000 conj3 . -1  ok
zdup cardinality . 87  ok
cr zet.
{65,754,2305,3425,3970,6401,14657,15634,37186,50177,58565,59053,59098,59218,69049,82945,118673,146210,257074,262145,262873,302497,319841,334177,389377,401441,455626,496241,508274,529985,921601,941041,1048577,1048601,1242793,1476226,1569061,1750393,1837097,2566561,2944705,3067769,3317074,4093154,4101154,4194385,4213625,4484017,4584929,4735097,4783069,4798594,4916545,5303810,5592434,5646001,5760001,5774602,5831545,8977273,8998393,9144577,9439993,9765746,9976306,10185529,11944561,12379505,13302409,13986466,14548594,15108770,15745025,15784466,15818497,15944098,16769026,16777337,16778441,17155426,18548777,19131877,23070401,23660897,23819585,24153953,33667138} ok

True so far. This take some time but I try 10000:

10000 conj3 . -1  ok
zdup cardinality . 129  ok
cr zet.
{65,754,2305,3425,3970,6401,14657,15634,37186,50177,58565,59053,59098,59218,69049,82945,118673,146210,257074,262145,262873,302497,319841,334177,389377,401441,455626,496241,508274,529985,921601,941041,1048577,1048601,1242793,1476226,1569061,1750393,1837097,2566561,2944705,3067769,3317074,4093154,4101154,4194385,4213625,4484017,4584929,4735097,4783069,4798594,4916545,5303810,5592434,5646001,5760001,5774602,5831545,8977273,8998393,9144577,9439993,9765746,9976306,10185529,11944561,12379505,13302409,13986466,14548594,15108770,15745025,15784466,15818497,15944098,16769026,16777337,16778441,17155426,18548777,19131877,23070401,23660897,23819585,24153953,26040898,31640674,31706945,32283521,33667138,34000562,37515986,37520281,38950162,39052481,39421505,40947202,40985921,43033601,43050817,43445377,44289026,44446210,47045882,47046137,47048690,56811506,64000361,64235537,65713618,66928882,66961570,68374489,68508353,70761674,73260281,73530626,85470281,87890626,88510465,93655426,94008377,96040001,96060226,118771553,123820633,140639489,141533305} ok

(To be continued)

Saturday, August 13, 2016

Instructions to create and manipulate sets

The basic words for sets are 

member \ element set -- flag
set= \ set1 set2 -- flag
subset \ set1 set2 -- flag

The parameters on the left sides above are located on the zst-stack. The 'element' could be a single (on the zst-stack) or a set. The flag is true or false on the ordinary stack. To check if a non negative single number on the parameter stack is a member in a set (located on the zst-stack), use the word

smember \ n set -- flag

3 { 1 2 3 4 } smember . -1  ok

Using member 

3 >zst { 1 2 3 4 } member . -1  ok

Except from set operations like

union \ s1 s2 -- s3
intersection \ s1 s2 -- s3
diff \ s1 s2 -- s3
powerset \ s1 -- s2     (s2 = set of all subsets of s1)
cartprod \ s1 s2 -- s3  (Cartesian product)
cardinality \ s1 -- n   (n = number of elements in s1)

and the possibility to create small sets

{ 10 10000 | prime } cardinality . 1225  ok

there are a lot of cryptic words to manipulate even rather big sets of non negative integers

intcond \ low hi xt -- | -- s   "intervall condition"
setcond \ xt -- | s -- s'       "set condition"
intimage \ low hi xt -- | -- s  "intervall image"
setimage \ xt -- | s -- s'      "set image"
paircond \ xt -- | s -- s'
pairimage \ xt -- | s -- s'
int2cond \ low hi n xt -- | -- s   "intervall two-condition"
int2image \ low hi n xt -- | -- s  "intervall image"
set2cond \ n xt -- | s -- s'       "set condition"
set2image \ n xt -- | s -- s'      "set image"

Inspired by the idea of orthogonal instructions I created a simple syntax just for set manipulations, to summarize and simplify the use of the words above:


variable zp

variable cf2

: condition  ' 0 cf2 ! sp@ zp ! ;
: function  ' 2 cf2 ! sp@ zp ! ;
: 2dim  ' -1 cf2 ! sp@ zp ! ;
: syntax  sp@ zp @ - 0= if 0 0 else 1 then cf2 @ ;

The word syntax check the number of input parameters and put a dummy parameter on the stack when needed.

(I have started to use the ANS-Forth notation for locals and will reform the code and the blog. It's awkward, but "forthish" awkward since it loads the parameters in the reversed direction: 

k l m n locals| n m l k |

It has some advantages even if it looks strange.)

The ten cryptic words are now squeezed into the three words

create-set
filter-set
transform-set


\ e.g. 1 20 condition < 7 create-set

: create-set \ m n xt nr -- set
  syntax locals| cf k nr xt n m |
  k cf or
  case 0 of m n xt intcond endof
       1 of m n nr xt int2cond endof
       2 of m n xt intimage endof
       3 of m n nr xt int2image endof
  endcase ;

\ e.g. condition > 5 filter-set
: filter-set \ set xt nr -- set'
  syntax locals| cf k nr xt |
  cf 0< if xt paircond exit then k
  case 0 of xt setcond endof
       1 of nr xt set2cond endof
  endcase ;

\ e.g. 2dim + transform-set
: transform-set \ set xt nr -- set'
  syntax locals| cf k nr xt |
  cf 0< if xt pairimage exit then k
  case 0 of xt setimage endof
       1 of nr xt set2image endof
  endcase ;

Creating sets:


1 25 condition prime create-set cr zet.

{2,3,5,7,11,13,17,19,23} ok

10 29 condition coprime 6 create-set cr zet.
{11,13,17,19,23,25} ok


1 10 function 2* create-set cr zet.

{2,4,6,8,10,12,14,16,18} ok

1 10 function * 3 create-set cr zet.
{3,6,9,12,15,18,21,24,27} ok

The word after condition/function must be a defined condition or function for one or two parameters.

Filter sets:

{ 1 25 | all } condition odd filter-set cr zet.
{1,3,5,7,9,11,13,15,17,19,21,23} ok

{ 1 25 | all } condition < 10 filter-set cr zet.
{1,2,3,4,5,6,7,8,9} ok

{ 1 2 3 } zdup cartprod zdup cr zet.
{(3,3),(3,2),(3,1),(2,3),(2,2),(2,1),(1,3),(1,2),(1,1)} ok
2dim < filter-set cr zet.
{(1,2),(1,3),(2,3)} ok

Transform sets:

{ 1 100 | prime } function 2* transform-set  ok
function 1- transform-set  ok
condition prime filter-set cr zet.
{3,5,13,37,61,73,157,193} ok

1 1000000 condition prime create-set  ok
condition < 50 filter-set  ok
function + 2 transform-set cr zet.
{4,5,7,9,13,15,19,21,25,31,33,39,43,45,49} ok

{ 1 10 | odd } zdup cartprod  ok
2dim + transform-set cr zet.
{2,4,6,8,10,12,14,16,18} ok

The word 2dim works like condition and function but acts on a set of pairs and can be used both for 2-dim conditions and 2-dim functions.

So far those instructions don't works in definitions and they just works for numbers and pairs of numbers.