functions of number theory

[AlfredFlaßhaar]

In Mathcad 14, I didn't find any functions or worksheets for using number theory functions. I am particularly interested in:

Factorization/prime number decomposition of a natural number as an ordered product of prime powers,
number of divisors of a natural number,
Euler function phi.
Are such functions implemented in MC14?

Happy New Year, Alfred Flasshaar

[LucMeekes]

Like this?

It's possible that not all work in Mathcad 14, but they do in Mathcad 11.

Success!
Luc

[Werner_E]

I fear that the prime number functions are not available in MC14/15!

[AlfredFlaßhaar]

Thanks for the hint. But I'm looking for algorithms for adults and not for school children ;-). An implemented function of the kind requested or a small program would be helpful. My programming knowledge comes from the Algol and Fortran times.

[AlanStevens]

"But I'm looking for algorithms for adults and not for school children "

This comment suggests you are looking for a math-intensive tool.  If so, then something like Maple (which has the functions you are interested in) would be of more use.

Alan

[ValeryOchkov]

List of Maple NumberTheory Package Commands
The following is a list of commands in the NumberTheory packag

AreCoprime
test whether a sequence of numbers is relatively prime
CalkinWilfSequence
compute the nth term in the Calkin-Wilf sequence
CarmichaelLambda
Carmichael's lambda function
ChineseRemainder
generalized Chinese remainder algorithm
ContinuedFraction
continued fraction expansion
ContinuedFractionPolynomial
simple continued fraction expansions for real roots of a rational polynomial
CyclotomicPolynomial
minimal polynomials of primitive roots of unity with rational coefficients
Divisors
the set of positive divisors of an integer
FactorNormEuclidean
factorization of integers in quadratic norm-Euclidean fields
HomogeneousDiophantine
solution to Minkowski's linear forms
ImaginaryUnit
modular square root of -1
InhomogeneousDiophantine
inhomogeneous Diophantine approximation
IntegralBasis
integral base of an algebraic number field
InverseTotient
inverse of Euler's totient function
IsCyclotomicPolynomial
test whether a polynomial is cyclotomic
IsMersenne
test whether a number is a Mersenne number
IsSquareFree
test whether an integer is square free
IthFermat
Fermat numbers
IthMersenne
Mersenne exponents
JacobiSymbol
generalized Legendre symbol
JordanTotient
Jordan's totient function
KroneckerSymbol
generalized Jacobi symbol
Landau
compute the Landau g function
LargestNthPower
largest integer power divisor of a number
LegendreSymbol
quadratic residuosity
ModExtendedGCD
solutions to the modulo n extended GCD problem
ModularLog
discrete logarithm under modular arithmetics
ModularRoot
modular root
ModularSquareRoot
modular square root
Moebius
Möbius function
MultiplicativeOrder
order of a number under modular multiplication
NearestLatticePoint
solution to the nearby lattice point problem
NextSafePrime
least safe prime greater than a number
NumberOfIrreduciblePolynomials
number of monic irreducible polynomials
NumberOfPrimeFactors
number of prime factors counted with multiplicity
PrimeCounting
number of prime numbers less than a number
PrimeFactors
prime factors of an integer
PrimitiveRoot
primitive root modulo n
PseudoPrimitiveRoot
pseudo primitive root modulo n
QuadraticResidue
quadratic residuosity of a number
Radical
radical of an integer
RepeatingDecimal
rational number in repeating decimal form
RootsOfUnity
modular roots of unity
SimplestRational
compute the simplest rational number in a real interval
SumOfDivisors
sum of powers of the divisors
SumOfSquares
solutions to the sum of two squares problem
ThueSolve
solutions to a Thue equation or inequality
Totient
Euler's totient function

[ValeryOchkov]

[Werner_E · Accepted solution]

Number theory was definitely the domain of the old genius programme Derive. This was bought up by Texas Instruments and distribution was then later discontinued. Nevertheless, there are still sites from which you can download a 30-day demo version of the programme.
http://www.austromath.at/daten/derive/derivedemo.htm
However, I don't know if there is still a legal way to purchase a licence key for the permanent use of the programme.

There has been a magazine since 1991, the Derive User Group Newsletter, which I was recently surprised to discover is still published online and freely available. D-N-L #128 was published last December. All 128 booklets are available here for free

http://www.austromath.at/dug/

I have particularly fond memories of Johann Wiesenbauer's contributions in the D-N-L.

So if you are curious you may give it a try, and, I am not sure, but some contributions might be valuable even without having Derive at hand.

It sure might be possible to create the functions you are looking for in Mathcad or even in Prime, but they would be rather slow and limited to IEEE floating point with all its drawbacks (Derive used internally integers only and implemented their own calc routines to deal with really large integers - the limit was only the memory installed).

Just for demonstration I add a sheet which I posted here quite some time ago when someone has a question to prime twins and prime cousins, etc.

I now added a function to factorize numbers and then it was easy to also write the Euler phi function or a function for the number of divisors.

But be aware that things really get slow when it comes to numbers with very large prime factors!

And in no way I claim that my implementations are optimized for running speed and memory usage. They are certainly not, and there is still a lot of room for improvement.

EDIT: Added Function to return the set of all divisors (quite inefficient) and a divisor function (returns sum of powers of divisors).

EDIT2: Added a far more efficient "Teiler" function to return a vector with all divisors.

TODO: make the old  prime number functions accessible for symbolic evaluation
             speed up prime number functions (nextPrime, etc.)

[LouP]

Werner - can you save your xmcdz file in a mathcad 11 version and post that?

Luc - you posted some prime # functions that work in MCD11 symbolics. I was looking in my notes/old files for other (undocumented?) symbolic modifiers that work in MCD11. Specifically, I recall at least two: trig and exponential. I found trig down one level in the symbolic Modifiers, but haven't figured out how to use it. Do you have a catalog of undocumented symbolic functions for MCD11, and use examples?

Lou

[Werner_E]

---

@LouP wrote:

Werner - can you save your xmcdz file in a mathcad 11 version and post that?

---

Sure, here you are!

[AlfredFlaßhaar]

Many Thanks. The small programs help a lot. I no longer have to count my fingers sore, although my generation still learned arithmetic with pen and paper and many wastepaper baskets were filled in the process. I have to admit that programming is not my forte. I feel more at home near Hausdorff's theorem. But at the moment I have the opportunity to deal with arithmetic problems from number theory. I can enjoy that now, while trying to get a gut feel for the thinking of great mathematicians of the past.