This tag concerns computational problems central to mathematical and scientific computating. The scope includes algorithms, numerical analysis, optimization, and linear algebra, computational topology, computational geometry, symbolic methods, and inverse problems.

learn more… | top users | synonyms

0
votes
2answers
23 views

Newton Raphson Example help

For h:= $\mathbb{R} \rightarrow \mathbb{R}, x \rightarrow e^{x}-x^2+1$ I know the formula as $$X_{n+1}=X_{n}-\frac{f(X_{n})}{f'(X_{n})}$$ so this would give me: $$ ...
1
vote
0answers
31 views

R $\subseteq \omega$ recursive iff $\exists m \in \omega$ such that $R=\{n \ | \ \bar{\omega} \models \phi[m,n] \}$.

The queston I'm trying to solve is use Kleene's enumeration theorem to show R $\subseteq \omega$ recursive iff $\exists m$ such that $R=\{n \ | \ \bar{\omega} \models \phi[m,n] \}$ for some $m \in ...
1
vote
0answers
33 views

Normalizing an elliptic curve to find integer solutions

I have an elliptic curve $$ c_1y^2 + a_1xy + a_3 = c_2x^3 + a_2x^2 + a_4x + a_6 $$ with integers $a_1,a_2,a_3,a_4,a_6,c_1,c_2$ and I would like to find all integer solutions of this elliptic curve. I ...
3
votes
0answers
67 views
+50

A conjecture about the prime function $p_n$

While testing my system Zet for computational mathematics I find possible relations now and then. The latest is: Conjecture: For all $(m,n)\in\mathbb Z_+^2$ except $(3,4),(4,3) \text{ and } ...
10
votes
6answers
549 views

Calculating logs and fractional exponents by hand

In view of what we can compute by hand, on a piece of paper, without having to use a computer or a calculator, how far can we go with the evaluation of $\log$-functions and fractional powers? More ...
0
votes
0answers
10 views

Determine an algorithm for $LU$ factorization and determine the number of operations [duplicate]

Suppose that $A\in\mathbb{R}^{n\times n}$ is a nonsingular matrix and that $A = LU$ is its $LU$ factorization. Give an algorithm that can compute, $e_i^{T}A^{-1}e_j$, i.e., the $(i,j)$ elements of ...
0
votes
0answers
7 views

Determine an efficient algorithm and describe the computational/storage complexity

Recall that a unit lower triangular matrix $L\in\mathbb{R}^{n\times n}$ is a lower triangular matrix with diagonal elements $e_i^{T}L e_i = \lambda_{ii} = 1$. An elementary unit lower triangular ...
2
votes
5answers
110 views

Minimize $a^5+b^5+c^5+d^5+e^5 = p^4+q^4+r^4+s^4 = x^3+y^3+z^3 = m^2 + n^2$ with distinct positive integers

Find the minimum value of the following: $$a^5+b^5+c^5+d^5+e^5 = p^4+q^4+r^4+s^4 = x^3+y^3+z^3 = m^2 + n^2$$ where all numbers are different/distinct positive integers. I know the answer (see ...
0
votes
1answer
23 views

Write column form elementary matrix in terms of element form elementary matrices

Recall that any unit lower triangular matrix $L\in\mathbb{R}^{n\times n}$ can be written in factored form as \begin{equation} L = M_1 M_2\ldots M_{n-1} \end{equation} where $M_i = I + l_i ...
2
votes
1answer
41 views

For what value of k onwards is it pointless for a computer to compute the probability mass function of the Poisson distribution

I am asking my computer to compute the probability mass function of $X \sim \text{Pois}(\lambda)$, a Poisson random variable. The function is: $$\Pr(X = k) = \frac{{e^{-\lambda} \lambda^k }}{k!}$$ ...
1
vote
2answers
34 views

Could we find an element on finite field? [closed]

Let $F$ be a finite field. Given an element $a^x$ in $F\setminus\{0\}$, could we find $a$?? I know that finding an integer $x$ is very hard problem (Discrete Logarithm Problem). However, I don't know ...
6
votes
1answer
79 views

Given two algebraic conjugates $\alpha,\beta$ and their minimal polynomial, find a polynomial that vanishes at $\alpha\beta$ in a efficient way

Inspired by this question, I was wondering about the following problem. $\alpha,\beta,\gamma,\ldots$ are the roots of an irreducible polynomial over $\mathbb{Q}$. How to compute the coefficients ...
2
votes
1answer
64 views

Is this polynomial time for greatest prime factor of odd numbers?

For natural numbers $n$ and $x,$ the number of $n^{th}$ roots that have $x$ in the whole numbers place can be represented as $(x+1)^{n}-x^{n}.$ For $p$ prime, $(x+1)^{n}-x^{n}-1\equiv0\bmod p$ iff ...
1
vote
1answer
41 views

Generating all prime powers $\leq N$

Some very good algorithms exist to generate all primes $p$ up to some bound $N$, like the sieve of Erastothenes and the sieve of Atkin. However, suppose I want to generate a (sorted) list of all prime ...
2
votes
1answer
45 views

Mysterious functions

I originally asked the following question in stackoverflow, but the question is closed because some members meant that the question is about math(see the following thread) So I will give a try here: ...
0
votes
1answer
19 views

Number system question

Is it true that if we are given a number system with base 3, mantissa 2, $-1 \le p \le 1$, determined by $$\pm 0.d_1 d_2 \times 3^p$$ where each number is normalized, unless it is zero, then the ...
3
votes
1answer
47 views

Conjecture about odd primes

For each odd prime $p$ there exist $n\in\mathbb{N}$ such that $p\equiv n^2 \text{ (mod }\varphi(n^2))$, where $\varphi$ is Euler's totient function. I'm developing my Forth based computational ...
1
vote
0answers
24 views

Ordering of elements in the base of a group

In section 4.6.7 of HANDBOOK OF COMPUTATIONAL GROUP THEORY, the authors use an ordering $\prec$ for the elements in a coset. That ordering, $\prec$, was defined in section 4.6 as follows. Throughout ...
0
votes
2answers
39 views

A matrix of a single 1 in each row and 0 elsewhere

Is there a particular name given to a matrix of m rows and n columns such that it must have one and only one 1 in each row and 0 elsewhere? For instance: ...
0
votes
0answers
14 views

Nature of state - recursion?

I always wondered how mathematicians define state (or rather: where it comes from?). This is tricky, because I always thought that in math there is only one "thing" - a pure, stateless function. Few ...
0
votes
0answers
14 views

Getting the most weekend for a specific date

Is there a formula that can find all the date(s) that fall on weekend the most times given a range of years. Example: Let say that it is given that the min year as 2000 and max year as 2005. and ...
0
votes
0answers
12 views

Finding a quadratic function the bounds any function below.

Given a function $f(x)$ I need to find another function $g(x)$, where $g(x) = Ax^2 + C$, where $A$ and $C$ are constants, such that $g(x) \le f(x)$, for all $x$. I can use a computer to do this for me ...
2
votes
1answer
24 views

What is the algorithm used by Matlab for computing the Bessel function?

I am quite curious about the algorithm behind. It is definitely not the power series expansion, right? So, what is the trick? I cannot find it in the help file of Matlab.
1
vote
0answers
13 views

Good numerical method for finding the eigenvalues and eigenfunctions of the Dirichlet-Laplacian?

Let us confine ourselves to 2D. What is the best numerical method for solving the eigenvalues and eigenfunctions of the Dirichlet-Laplacian operator? Possibly, it depends on the shape of the domain? ...
-1
votes
0answers
18 views

Rejection method in R

I need to generate pseudo random numbers using the rejection method in R X is a random variable normally distributed N(6,1). I did as follows, but I get a error message. Can someone give me a hint? ...
-2
votes
0answers
56 views

What are the Correct Conditions for Akra-Bazzi Master Theorem?

The Akra-Bazzi method solves recurrences of the form: $$T(n) = g(n) + \sum\limits_{i=1}^k a_iT(b_in + h_i(n))$$ In the Wikipedia article about the topic, it says that the condition on $g(n)$ is: ...
1
vote
0answers
25 views

How to use CVXOPT to solve an semidefinite programming problem

I'm using Sage to solve a problem and would like to use cvxopt to solve a sdp problem. Specifically, I have a list of expressions of the form $$c + \sum_{i,j} a_{i,j} q_{i,j}$$ where each $c$ and all ...
1
vote
1answer
24 views

Can gauss quadrature integrate this function exactly $f(x) = \frac{2x}{\sqrt{x^3 + 2x + 5}}$?

Suppose I had a function $$f(x) = \frac{2x}{\sqrt{x^3 + 2x + 5}},$$ that I wanted to integrate on the interval $[\pi, 2\pi]$. Can Gauss quadrature of order $2$ (ie. with two points ...
0
votes
0answers
14 views

Help with Hidden Markov model and SMC methods

So its quite a long background i don't really know where to start but here goes. The background is as follows: Background Observation model As the target is moving, it measures the signal (RSSI) ...
0
votes
1answer
36 views

Is the problem decidable with Turing machine M that inputs x,y,z does M halts on these 3 instances

Is the following problem is decidable? Given a Turing machine M inputs x,y,z does M halts on these 3 instances? Hint: make y and z any two artificial inputs that the program stops with these inputs. ...
0
votes
0answers
34 views

Positivity of the last component of non negative least squares based on active set method

I have followed the instructions given in Lawson and Hanson book for non-negative least squares using active set method. I am having a trouble in justifying one of the statements they have made about ...
0
votes
1answer
30 views

Finding distance from valid number

I have a game related problem that is pretty complex. Here is the simplified version of the problem. I have a list of "good" numbers. ...
0
votes
0answers
20 views

Computationally check for roots/positiveness of a big polynomial in a given interval

For a proof, I need to check that given a little interval $(0, 0.28)$ some concrete polynomials $\in \mathbb{Q}[w]$ (polynomials in one variable ranging over the real numbers, with degrees around 50) ...
0
votes
0answers
20 views

Help with a proof of the computability of the monus function by recursion

Reading a text on computability by a guy called Cutland, and he basically asserts the following, which is suppose to be a proof by recursion that x ∸ 1 is a computable function: (1) 0 ∸ 1 = 0 (2) ...
1
vote
1answer
24 views

compute probability density function of a bivariate function without sampling

Suppose $X_1 \sim f_{X_1}(x_1)$, $X_2 \sim f_{X_2}(x_2)$ are random variables with known probability density function. Is there any way to compute the probability density function of a bivariate ...
1
vote
1answer
44 views

How to find b ( the most efficient way) in $ax^2+bxy+ cy^2$?

I know the very basic way to find the b in this quadratic expression: $$P(x,y)=ax^2+bxy+ cy^2$$ I can first evaluate $P(0,1)=c$. Similarly, I can do $P(1,0)=a$ and then I can do ...
0
votes
0answers
11 views

solving a self-consistency relation.

I would like to solve a self-consistency relation analytically or numerically. The self-consistency relation is: Sigma = int_{-pi}^{pi} dk 1/(E_F - cos(k) - Sigma) Does someone know the best ...
0
votes
1answer
21 views

Simple Formula to workout intervals

Say we have scale from $1$ to $12$ We pick two numbers on this scale and trying to figure the shortest distance. Say $x_1 = 2, x_2 = 4$ and we need to figure out y which in this case would be $y = 2$ ...
1
vote
0answers
53 views

Looking for a perfect square

I have a base number and I add to this number in increments. Is it possible to calculate where is the nearest perfect square without going through all the numbers? Example: Base number 11 Increment ...
1
vote
0answers
31 views

How to find the ground energy state solution in a quantum harmonic oscillator?

Recently, I came across a question which asks to solve the Schrödinger equation for a harmonic oscillator on $ [a, b] $ : $-\frac{\hbar^2}{2m}\frac{d^2\psi}{d x^2} + \frac{1}{2} m \omega^2 x^2 \psi = ...
1
vote
1answer
32 views

n-th number with given prime divisors

I would like to compute th $n$-th positive integer whose prime divisors are among numbers $2$, $3$ and $5$. $n$ is at most $12500$. My first approach was sieving but i found out that there are less ...
9
votes
1answer
218 views

How many numbers $ N \le 10^{10}$ are the product of $3$ distinct primes?

How many numbers $ N \le10^{10}$ are the product of $3$ distinct primes? I can realistically calculate any $\pi(n), n < 10^{15} $ but I don't think it's possible to list all primes $>10^8$ in ...
0
votes
2answers
23 views

Are there alternatives to polygons in mathematical (computational) modelling?

So polygons are pretty standard in computer graphics, but from a mathematical perspective, one'd expect something more refined and sophisticated to be possible right? Polygons are not very ...
0
votes
0answers
9 views

Understanding the bound given by Johnson–Lindenstrauss lemma

Here I choose to use the statement made by S.Dasgupta: For any $0<\epsilon<1$ and any integer $n$, let $k$ be a positive integer s.t. $$k \geq 4(\epsilon^2/2-\epsilon^3/3)^{-1} \ln n $$ Then ...
2
votes
0answers
25 views

Egyptian fraction with least possible sum

Suppose that $~a~$ and $~b~$ are coprime positive integers. Then there exists representation of $~\frac{a}{b}~$ as egyptian fraction: $$~\frac{a}{b} = \frac{1}{d_1} + \cdots + \frac{1}{d_s} ~$$ There ...
1
vote
1answer
23 views

Algorithm for generating all elements of a set consisting of specific $n$-tuples

I was working on functional analysis last night, and then my mind got distracted by the following problem. Consider a set $$I=\{0,1\}$$Now consider a subset of $\mathbb{R^n}$ $$X=\{(x_1,x_2,\dots ...
4
votes
2answers
77 views

Strange divisors

Let $~m~$ and $~n~$ be positive integers. Let's call (my term - not sure there is any official term for such thing) number $~m~$ a "strange divisor" of number $~n~$ if dividing $~n~$ by $~m~$ we get ...
3
votes
2answers
90 views

What programing language Thomas Hales used in 1998 to prove Kepler’s conjecture?

Mathematicians have been studying sphere packings since at least 1611, when Johannes Kepler conjectured that the densest way to pack together equal-sized spheres in space is the familiar pyramidal ...
0
votes
1answer
109 views

Pseudo-primality test for Mersenne numbers faster than Lucas-Lehmer test?

Definition Let $M_p=2^p-1$ with $p$ prime and $p>2$ . Lucas-Lehmer Test $M_p$ is prime if and only if $S_{p-2} \equiv 0 \pmod {M_p}$ where $S_{k+1}=S^2_{k}-2$ and $S_0=4$ . Pseudo-Primality ...
1
vote
1answer
50 views

Find binomial coefficient by its value

Given any positive integer $~m~$ there always exist pair of positive integers $~(n,k)~$ such that $~\binom{n}{k} = m~$. At least we can take $~n = m~$ and $~k = 1~$. How can we efficiently find all ...