Skip to main content

All Questions

17 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
15 votes
0 answers
487 views

Word complexity of primes mod 4

For an infinite binary word $w$, the word complexity $f_w(n)$ is defined as the number of different subwords of length $n$. The asymptotic behavior of this function is an important parameter of the ...
Igor Pak's user avatar
  • 17k
5 votes
0 answers
161 views

Consecutive integers each of which has a large prime factor

There are many results about consecutive integers all having small prime factors. But what about consecutive integers each of which has a large prime factor? More precisely, let $P(n)$ be the ...
Penchez's user avatar
  • 341
5 votes
0 answers
176 views

Can the integers in an easily computable sequence free of prime numbers always be factored easily?

Call a sequence $(a_n)$ of positive integers easily computable if there is a constant $C$ and an algorithm which computes $a_n$ from $n$, $a_1, \dots, a_{n-1}$ and a finite number of integer ...
Stefan Kohl's user avatar
  • 19.6k
4 votes
0 answers
306 views

How to explain this number-theoretic seeming “almost coincidence”?

For natural numbers $n\geq2$, let $d(n)$ be the number of divisors of $n$, and let \begin{equation} g(n)=n\sum_i r_i(p_i-1) \end{equation} where $n=\prod_i p_i^{r_i}$ is the factorisation of $n$ as a ...
Simon's user avatar
  • 141
4 votes
0 answers
178 views

Primitive roots modulo primes related to Fibonacci numbers or Lucas numbers

The Fibonacci numbers $F_0,F_1,F_2,\ldots$ and the Lucas numbers $L_0,L_1,L_2,\ldots$ are given by $$F_0=0,\ F_1=1,\ \text{and}\ F_{n+1}=F_n+F_{n-1}\ (n=1,2,3,\ldots)$$ and $$L_0=2,\ L_1=1,\ \text{...
Zhi-Wei Sun's user avatar
  • 15.6k
2 votes
0 answers
76 views

upper and lower bounds on rowlands sequence

rowlands sequence is defined as follows \begin{equation} a_{n}=a_{n-1} + b_{n} \end{equation} where $b_{n} = gcd(a_{n-1}, n)$ for $n>h$ it originates from E. Rowlands 2008 paper "A Natural ...
Antisocialfreal's user avatar
2 votes
0 answers
157 views

Conjecture: $x^4+1$ is never Wieferich prime

Related to this question and Alexander Kalmynin's answer. For natural $n$ define $J(n)=(2^{n-1}-1) \bmod n^2$ and if $n$ is power of two define $J(2^n)=1$ (this is artificial, just to avoid triviality ...
joro's user avatar
  • 25.4k
2 votes
0 answers
199 views

Not a twin prime pair test using $\gcd$ only

Let $m$ be an odd positive integer such that $m=2k+1$, $k\in\mathbb{N}$. Let $v$ be a vector of $n$ positive integers. Let $v(i)$ be the $i$-th element of the vector. Then we start with $v(i)=m(i+1)-2$...
Notamathematician's user avatar
2 votes
0 answers
108 views

How to compute/estimate the least $k$ such that there exist $n$ consecutive integers each having a prime factor $\le k$?

Let $a_n$ be the least integer $k$ such that there exist $n$ consecutive integers each with a prime factor $\le k$. For example, $a_{13} \le 11$ because the 13 consecutive integers $114,115,\ldots,126$...
tuna's user avatar
  • 523
2 votes
0 answers
326 views

Why can one compute the sum of divisors of $n$ without factoring $n$?

Question links to paper which states: $$ \sigma(n)= \frac{6}{n^2(n-1)}\sum_{k=1}^{n-1}(3n^2-10k^2)\sigma(k)\sigma(n-k) \qquad (1) $$ where $\sigma(n)$ is the sum of divisors of $n$. Another similar ...
joro's user avatar
  • 25.4k
2 votes
0 answers
311 views

A question concerning the strange arithmetic derivation

This question is related to Strange (or stupid) arithmetic derivation. The original question whether an unbounded sequence of iterates exists is still unanswered. $$n=\prod_{i=1}^{k}p_i^{\alpha_i} \...
István Kovács's user avatar
1 vote
0 answers
102 views

Curious congruences modulo $4$ involving primes

We define $$S(n)=\sum_{a=2+(n\pmod 2)}^{n-2} \sharp(\{j,1\leq j<n \pmod{a},(a,j)=1\})\ .$$ (Searching the OEIS yielded no results.) For $n>2$ we have the following experimental observations (...
Roland Bacher's user avatar
1 vote
0 answers
60 views

On the parity of $(2^{\varphi(n)}-1) \bmod{n^2}$

For odd integer $n$ define the function $$ J(n)=(2^{\varphi(n)}-1) \bmod{n^2}$$ $J(n)$ is integer in $[0,n^2-1]$ and it is divisible by $n$. Integer $n$ is Wieferich number iff $J(n)=0$ and if $n$ is ...
joro's user avatar
  • 25.4k
1 vote
0 answers
153 views

A definition related to pseudoprimes and the Dedekind psi function

In this post we consider that $\psi(k)$ denotes the Dedekind psi function. Wikipedia has an artcle dedicated to this arithmetic function Dedekind psi function defined for a positive integers $m>1$ ...
user142929's user avatar
1 vote
0 answers
151 views

On smoothness and roughness of a number related to triangular numbers

Define $\triangle_n$ to be the $n$th triangular number. Define $$M_n=(2\triangle_n-1)2\triangle_n(2\triangle_n+1)=2\triangle_n(4\triangle_n^2-1).$$ Define $(\ell,k)$-smough numbers to be numbers that ...
VS.'s user avatar
  • 1,826
1 vote
0 answers
223 views

Does each prime $p>3$ have a quadratic nonresidue which is a Mersenne number?

Recall that the Mersenne numbers are those integers $M_p=2^p-1$ with $p$ prime. QUESTION: Is it true that for each prime $p>3$ there is a Mersenne number which is a quadratic nonresidue modulo $p$?...
Zhi-Wei Sun's user avatar
  • 15.6k
0 votes
0 answers
110 views

What will be the set of non-Wieferich numbers if the set of non-Wieferich primes is finite?

Integer $n$ is Wieferich number if $2^{\phi(n)}-1 \equiv 0 \pmod {n^2}$. Wieferich prime is Wieferich number with $n$ prime. It is an open problem if there are infinitely many Wieferich primes and ...
joro's user avatar
  • 25.4k