## Sunday, May 15, 2016

### Words for testing conjectures

Making code for testing conjectures can be cumbersome even in the case of easy programming. So far in Zet there is the possibility of make and calculate with sets of numbers interactively.

{ 1 1000 | prime } ok
{ 1 1000 | pairprime } { 1 1000 | notpairprime }
union ok

zet= . -1 ok

Conditions so far are
: all dup = ;
: odd 1 and ;
: 1mod4 4 mod 1 = ;
: 3mod4 4 mod 3 = ;
: sqr dup sqrtf dup * = ;
: sqrfree dup radical = ;
: pairprime dup prime over 2 + prime rot 2 - prime or and ;
: notpairprime dup prime swap pairprime 0= and ;
: semiprime bigomega 2 = ;  \ A product of two primes?
: uniprime smallomega 1 = ; \ Only divisional by one prime?
: biprime smallomega 2 = ;  \ Exact two different primes?

The construction { 1 10000 | pairprime } is fancy but slow and risk overflow in data stack. All the pairprimes in the intervall will first be created on the stack and then be moved to the zst-stack. It's better to check number for number and create the set directly on the zst-stack.

: intcond \ low hi xt -- | -- s   "intervall condition"

loc{ xt }
swap 0 -rot
do i xt execute
if i >zst 1+ then
loop 2* negate >zst ;

utime 1 100000 ' pairprime intcond utime cr d- d. cardinality .

-35954 2447  ok

A set of 2447 primes is created in about 0.04 seconds. This construction is also possible to use in definitions, then using ['] instead of '.

To filtrate a set on the zst-stack:

: setcond \ xt -- | s -- s'       "set condition"
loc{ xt } 0
foreach
do zst> dup xt execute
if >xst 1+ else drop then
loop dup 0
do xst> >zst
loop 2* negate >zst ;

{ 1 100 | prime } ' 1mod4 setcond cr zet.

{5,13,17,29,37,41,53,61,73,89,97} ok

It's also nice to be able to create the image of a function:

: intimage \ low hi xt -- | -- s  "intervall image"
loc{ xt }
swap 2dup
do i xt execute >zst
loop - 2* negate >zst
set-sort reduce ;

: setimage \ xt -- | s -- s'      "set image"

loc{ xt } 0
foreach
do zst> xt execute >xst 1+
loop dup 0
do xst> >zst
loop 2* negate >zst
set-sort reduce ;

Functions so far are:

log~ ( n -- nr ) where nr=1+²log n
random ( u1 -- u2 ) where 0≤u2<u1
nextprime ( numb -- prime )
prevprime ( numb -- prime )
sqrtf ( m -- n ) "floor"
sqrtc ( m -- n ) "ceiling"
radical ( n -- r )
totients ( n -- t )
bigomega ( n -- b )
smallomega ( n -- s )
ufaculty ( u -- u! )
pnr@ ( n -- p ) prime number n
pi ( x -- n ) number of primes ≤ x

Functions and conditions both must have the stackdiagram ( m -- n ), but the concept will be generalized.

1 20 ' radical intimage zet. {1,2,3,5,6,7,10,11,13,14,15,17,19} ok

Some test functions:

: square dup * ;                \ x → x²
: sqr>prime square nextprime ;  \ x → nextprime(x²)
: sqr<prime square prevprime ;  \ x → prevprime(x²)
: foo dup totients mod ;        \ x → x(mod ϕ(x)) Euler's totient.

{ 1 100 | all } ' foo setimage cr zet.
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,21,22,23,25,27,31,33,35,39} ok

1 100 ' square intimage ' foo setimage cr zet.
{0,3,5,7,11,13,17,19,20,23,27,28,29,31,37,41,43,44,47,52,53,59,61,67,68,71,73,76,79,80,83,89,92,97,105,112,116,124,125,148,164,172,176,180,188,189,208,243,252,272,304,320,343,368,385,396,429,448,468,500,585,704,720,825,945,969,1008,1105,1197,1280,1309,1372,1540,1620,1701,1725,1729,1785,2185,2187,2625,2697,3069,3861} ok

Hmm, it seems like all odd primes less than 100 belongs to the image...

1 10000 ' square intimage ' foo setimage ok
1 10000 ' prime intcond ok
zswap diff zet. {2} ok

So I asked Mathematics stack exchange about it. (:

Well, it might be sound to expect non dramatic explanations to conjectures, especially conjectures concerning primes.

To check relations R m there is a need for testing subsets of Cartesian products, sets of pairs of integers.

: paircond \ xt -- | s -- s'
loc{ xt } 0
foreach
do zdup zet> drop xt execute
if zst xst setmove 1+ else zdrop then
loop 6 * negate >xst
xst zst setmove ;

{ 1 10 | all } zdup cartprod ' = paircond cr zet.

{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9)} ok

: pairimage \ xt -- | s -- s'
loc{ xt } 0
foreach
do 1+ zet> drop xt execute >xst
loop dup 0
do xst> >zst
loop 2* negate >zst
set-sort reduce ;

{ 2 10 | all } zdup cartprod ' * pairimage cr zet.
{4,6,8,9,10,12,14,15,16,18,20,21,24,25,27,28,30,32,35,36,40,42,45,48,49,54,56,63,64,72,81} ok

Some conditions and functions N²→N are =, <>, <, >, >=, <=, +, *, /, mod, **, ugcd, -, invmod, legendre, jacobi, kronecker, gnorm, choose, where m ≥ n for m n - and m n must be coprime for m n invmod. the gnorm of two integers m n is the norm of the gaussian integer m+in, that is the number m²+n².

: coprime ugcd 1 = ;
: divide swap mod 0= ;

{ 1 10 | all } zdup cartprod ' coprime paircond cr zet.
{(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(2,1),(2,3),(2,5),(2,7),(2,9),(3,1),(3,2),(3,4),(3,5),(3,7),(3,8),(4,1),(4,3),(4,5),(4,7),(4,9),(5,1),(5,2),(5,3),(5,4),(5,6),(5,7),(5,8),(5,9),(6,1),(6,5),(6,7),(7,1),(7,2),(7,3),(7,4),(7,5),(7,6),(7,8),(7,9),(8,1),(8,3),(8,5),(8,7),(8,9),(9,1),(9,2),(9,4),(9,5),(9,7),(9,8)} ok

{ 1 10 | all } zdup cartprod ' divide paircond cr zet.
{(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(2,2),(2,4),(2,6),(2,8),(3,3),(3,6),(3,9),(4,4),(4,8),(5,5),(6,6),(7,7),(8,8),(9,9)} ok

{ 1 10 | all } zdup cartprod ' coprime paircond ' gnorm pairimage cr zet.
{2,5,10,13,17,25,26,29,34,37,41,50,53,58,61,65,73,74,82,85,89,97,106,113,130,145} ok