Questions on the number-theoretic functionality of Mathematica.

learn more… | top users | synonyms

19
votes
2answers
325 views

Speeding up the built-in Rudin-Shapiro and Thue-Morse sequence functions

Version 10.2 introduced two well-studied sequences as functions: the (Golay-)Rudin-Shapiro sequence (RudinShapiro[]) and the (Prouhet-)Thue-Morse sequence (...
0
votes
0answers
8 views

Proof for sum of divisor of a given range [migrated]

Question is like this: We are given a number "n"(n<=10^7) and we have to calculate G(n) which is G(n)=F(1)+F(2)+F(3)+F(4)+....F(n). where F(x) is the sum ...
0
votes
0answers
36 views

How to print intermediate steps of simplifying a power formula? [duplicate]

To answer the question of proving Fibonacci sequence is periodic mod 5 without using induction., I came across Mathematica to prove $$F_{n}\equiv F_{n+20}\pmod 5$$ for all $n \geq 2$ I defined: ...
6
votes
3answers
177 views

On a strange pattern of triangular numbers in Ulam's spiral

In this MSE post, user GeMir noticed that, where the green dots are the triangular numbers, $$T_n = \frac{n(n+1)}{2} = 1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,\dots$$ in the Ulam spiral ...
0
votes
1answer
48 views

Write a function pollard[n, B] that tries to factor an integer n, using Pollard's p − 1 method with at most B iterations [closed]

This is what I got but it seems it's not working. When I test it, it just goes through and nothing gets returned. Is there something I'm missing? ...
4
votes
2answers
71 views

Iterative Tree Plot for the Sum of an Integer's Digits Squared

I am trying to make a graph that depicts integers<100 mapping to the sum of their digits squared. I can do this for one iteration, but I don't know how to do it for more than one, or until the new ...
0
votes
0answers
39 views

Dirichlet series expansion

Is there a way to get Dirichlet series expansions in Mathematica? For example, I would want DirichletSeries[Zeta[s], {s, 4}] to return ...
22
votes
2answers
1k views

Trying to Visualize a Collatz - The Collatz conjecture

So I'm new in this and learning--- and I happen to have this collatz collatz[x_, y_] := If[x == 3*y || x == 2*y + 1 || y == 3*x || y == 2*x + 2, 2, 0] So i want ...
0
votes
1answer
153 views

Prime number The Ulam spiral [closed]

I want a simple method of visualizing the prime numbers that reveals the apparent tendency of certain quadratic polynomials to generate unusually large numbers of primes. I was able to display the ...
5
votes
1answer
113 views

Find all “chains” in the poset of divisors

I want to input a set of divisors of an integer $n$ and return all subsets of these divisors ${d_1,d_2,...d_k=n}$ such that $d_1$ divides $d_2$, $d_2$ divides $d_3$, ... and $d_(k-1)$ divides $d_k$. I ...
3
votes
4answers
237 views

Permuted Prime Numbers

How can I produce all 3-digit and 4-digit prime numbers [100-9999] in which, all permutations of all digits produce again a prime number, such as 311, 131, 113, ...
9
votes
1answer
224 views

Possible improvements to this Syracuse (3x+1)/2 graph?

This algorithm produces the Syracuse disjoint tree graph without any duplicates. No need for Union, For, and ...
1
vote
3answers
135 views

List of prime powers

I have a list of not necessarily distinct prime powers. For example: {2,3,4,25,2,3}. I want to combine (multiply) the highest prime powers for each prime. In this case 25*3*4 = 300 since 25 is the ...
3
votes
1answer
167 views

How to further accelerate arithmetic with Fermat Pseudoprime and Fibonacci number

I've been working on this all night, and I have made this go pretty fast, compared to my first iteration of the program, but now I'm out of ideas. I'm trying to write a program to test (by good ...
2
votes
2answers
151 views

Recursive Euclidean algorithm in Mathematica

Can anyone explain to me how do I use a recursion, if I don't know the limit? For example, I need the remainder $r$ of the Euclidean algorithm for $\gcd(a,b)$ which equals $0$. I figured out that the ...
2
votes
2answers
88 views

Need help with code for number theory problem

I'm completely new to Mathematica (used previously only for very simple cases). I need to write a quite complex function. The function must do the following: Input consists of two numbers: a and b. ...
2
votes
1answer
130 views

Using the Baby-Step Giant-Step algorithm

Here is a concept I am working through: As part of an attack on an El-Gamal cipher, solving the discrete logarithm problem $$10^x = 532107 \;\, {\rm mod} \;\, 1313839.$$ Using the ...
0
votes
1answer
64 views

Factoring large integers with the Pollard p-1 method

I am trying to use the Pollard $p-1$ method to find the factors of a large integer. Here is the problem: An RSA-type cipher is based on the integer $n = 140016480344628383$ and exponent ...
9
votes
3answers
637 views

Proving (or at least 'being told by Mathematica') that Sqrt[2] is irrational?

I realize that Mathematica is not specifically an automated theorem prover. However, this article: http://www.wolfram.com/products/mathematica/newin6/content/EquationalTheoremProving/ Suggests that ...
4
votes
5answers
256 views

On finding all the positive integral solutions of $x^2+y^2=z^2+1$

I am a new to Mathematica. My goal is to find many (if not all) positive integer solutions to the equation: $x^2+y^2=z^2+1$ using Mathematica. However the problem is that I can only find a ...
0
votes
1answer
68 views

solving quadratic and linear congruences with different modulus

We are able to solve the quadratic congruences $C^2 + Q^4 - 2\equiv mod 3072$ and $C - Q^2 - 2046\equiv mod 3072$ by entering ...
1
vote
3answers
124 views

Expressing a series formula

I want to generate a series of the following kind in Mathematica: $\quad \quad a(n+1) = a(n) + ({\rm prime}(n+1) - 1)/2 \quad \mbox{for odd primes},$ so that the resultant series is ...
0
votes
1answer
46 views

How to “de rationalize” a number? [closed]

How can 1/2 be represented as 0.5? Thanks!
2
votes
1answer
110 views

What are the terms of the sequence generated by Zeta(3s)/Zeta(s)?

The LiouvilleLambda function has Dirichlet generating function of Zeta[2s]/Zeta[s]. I am curious about an analogous function with Dirichlet generating function of Zeta[3s]/Zeta[s]. Can Mathematica ...
0
votes
1answer
121 views

Finite Field matrix rank calculation

How does one define a matrix over $\mathrm{GF}(p^r)$ in Mathematica in order to compute rank? I am working with $\mathrm{GF}(2)$?
3
votes
2answers
108 views

Generating Z^*_n

I'm using Mathematica to illustrate basic number theory concepts in a graduate cryptography class. To generate elements of the multiplicative group of integers modulo $n$, i.e. $\mathbb{Z}^*_n$, I can ...
1
vote
2answers
81 views

Arithmetic on algebraic numbers

I'd like to perform some elementary operations on algebraic numbers. ...
3
votes
3answers
184 views

Code for (a,b) with gcd(a,b)=1?

I am trying to make a big table that includes all ordered pairs (a,b) with a (1,2) (1,3) (2,3) (1,4) (3,4) (1,5) (2,5) (3,5) (4,5) (1,6) (5,6) ... Any ideas? Thanks!
7
votes
5answers
527 views

Calculating weird numbers

A weird number is a number such that the sum of the proper divisors (divisors including 1 but not itself) of the number is greater than the number, but no subset of these divisors sums to to ...
14
votes
3answers
612 views

How can FactorInteger be so slow if PrimeQ is fast?

My 8th grade son had a homework problem to find a prime factor of $99!-1$. I thought to be clever/lazy and used FactorInteger[99!-1], but it takes forever. ...
6
votes
2answers
148 views

Number of divisors visualized with the QPochhammer function, how improve performance of code?

I have this code that is originally Jeffrey Stopple's code for the Riemann zeta function in the complex plane. Because I discovered yesterday that the number of divisors can be generated with the ...
12
votes
8answers
502 views

Find the minimum integer r such that $(10^r - 1)/37$ is an integer

I know Element[(10^r - 1)/37, Integers] tests the condition. So what is the command that gives me the minimum integer value r ...
4
votes
1answer
161 views

Ruth-Aaron quadruple challenge

This a computational challenge, to find an efficient algorithm to discover a quadruple $(n,n+1,n+2,n+3)$ with the same sum of prime factors as described in the MO question, "Ruth-Aaron triples, etc." ...
6
votes
3answers
381 views

Better answer to Santa's riddle about sum of a number's divisors?

I was hoping to find an elegant solution to this riddle, using only a line or two of Mathematica: Santa Claus was telling one of his elves: "If I multiply the age of three of my reindeer, I get ...
2
votes
1answer
61 views

Factoring an ideal in a number field into prime ideals

I'd like to factor an ideal in a number field into prime ideals, exactly as in this example from the Sage documentation: ...
2
votes
3answers
132 views

Can you compute more terms in this sequence?

I am trying to identify a sequence related to the von Mangoldt function matrix. Since I believe/conjecture that the columns in the matrix have period lengths as in this sequence b: ...
0
votes
0answers
94 views

Solution of a set of quadratic congruences (Chinese remainder)

Edit: Please remove this question. I think there are mathematics error in what I am asking. You are welcome to edit the question if you can state the problem correctly. I have a set of quadratic ...
2
votes
1answer
87 views

One of the factors greater than $x$ [closed]

Is there an easy way to tell Mathematica to find one of the prime factors of $n$ greater than $x$. For example, if $n=1299709\cdot 7919 \cdot 17$, is there a way to request a factor greater than ...
14
votes
6answers
1k views

Integers which are the sum of both two and three consecutive squares

This is a math problem I came across the other day: $365$ can be written as a sum of two and also three consecutive perfect squares: $365=14^2+13^2=12^2+11^2+10^2$ What is the next ...
1
vote
1answer
125 views

Mathematica spitting code back when using Resolve over a large range of interest

I've just started using Mathematica and have encountered my first issue. Below are two commands which only differ in the range of values I am asking Mathematica to check. The first works fine, but the ...
4
votes
2answers
278 views

Approximation to the prime counting function

Is there a function similar to PrimePi that gives approximate value for large numbers? In particular, I need a reasonably good approximation for $\pi(x)$, where ...
3
votes
6answers
403 views

Triangular numbers boolean function

I read the new book by Paul Wellin Programming in Mathematica. There is an exercise about triangular numbers. (The n-th triangular number is defined as the sum of ...
12
votes
1answer
425 views

the more effective method to find 21 digits armstrong number

In recreational number theory, a narcissistic number (also known as a pluperfect digital invariant (PPDI), an Armstrong number(after Michael F. Armstrong) or a plus perfect number) is a number that is ...
1
vote
5answers
279 views

Write a number as the product of its two largest divisors

For even n >= 10 && n <= 98 I want to write n as the product of its two largest divisors (excluding ...
3
votes
5answers
1k views

A question regarding 1 divided 243

Here is a problem due to Feynman. If you take 1 divided by 243 you get 0.004115226337 .... It goes a little cockeyed after 559 when you're carrying out the decimal expansion, but it soon straightens ...
6
votes
5answers
775 views

Write any positive integer as a sum of squares

With n = 17 I would like to get {4, 1} and with n = 999 {31, 6, 1, 1} so that, for example, ...
2
votes
1answer
106 views

Symbolic multiplicative partitions

Let $p_n\#\equiv\prod_{k=1}^{n}p_k$ (primorial): p[n_] := Times @@ Prime[Range[n]] then the multiplicative partitions of $p_{1,2,3,4}\#$ are $$ \{\{2\}\},$$$$ ...
3
votes
2answers
270 views

Multiplicative partition function

I am trying to create a multiplicative partition function that would generate something like ...
4
votes
4answers
282 views

Conveying density of 5-smooth (Hamming) numbers

A number is 5-smooth if its only prime factors are 2, 3 or 5. Example: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … Interesting thing is that as they become larger ...
8
votes
0answers
154 views

Is there a PrimeQ whose accuracy guarantee you can adjust?

Say I have a list of a million integers each with a million digits, and I want a crude sieve to see which have a chance at being prime. Mathematica has a PrimeQ function, which appears to be slow ...