All Questions
Tagged with integer-sequences nt.number-theory
106 questions with no upvoted or accepted answers
35
votes
0
answers
1k
views
Is there any positive integer sequence $c_{n+1}=\frac{c_n(c_n+n+d)}n$?
In a recent answer Max Alekseyev provided two recurrences of the form mentioned in the title which stay integer for a long time. However, they eventually fail.
QUESTION Is there any (added: ...
- 23.7k
32
votes
0
answers
2k
views
A question related to the Hofstadter–Conway \$10000 sequence
The Hofstadter–Conway \$10000 sequence is defined by the nested recurrence relation $$c(n) = c(c(n-1)) + c(n-c(n-1))$$ with $c(1) = c(2) = 1$. This sequence is A004001 and it is well-known that this ...
- 701
24
votes
0
answers
1k
views
Is A276175 integer-only?
The terms of the sequence A276123, defined by $a_0=a_1=a_2=1$ and $$a_n=\dfrac{(a_{n-1}+1)(a_{n-2}+1)}{a_{n-3}}\;,$$ are all integers (it's easy to prove that for all $n\geq2$, $a_n=\frac{9-3(-1)^n}{2}...
- 655
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 ...
- 17.1k
13
votes
0
answers
718
views
Is "OEIS A001935 Number of partitions with no even part repeated" efficiently computable $\mod 4$?
Is A001935 Number of partitions with no even part repeated efficiently computable $\mod 4$?
I am interested because of this relation with sum of divisors of $8n+1$.
$\sigma(8n+1) \equiv A001935(n) \...
- 25.4k
10
votes
0
answers
252
views
Permutation of positive integers
Let $a_n$ be a sequence such that $a_1=1$ and for each $n \geq 1$ $a_{n+1}$ is the smallest positive integer distinct from $a_1,a_2,...,a_n$ such that $\gcd(a_{n+1}a_n+1,a_i)=1$ for each $i=1,2,...,n$....
- 3,153
8
votes
0
answers
1k
views
Is the Collatz conjecture known to be true for interesting unbounded classes of numbers?
The Collatz or the $3n+1$ conjecture is open.
Is there a specific polynomial $f(x)\in\mathbb Z[x]$ whose range is unbounded for which every integer of form $|f(m)|$ at $m\in\mathbb Z$ satisfies $3n+1$...
- 13.9k
8
votes
0
answers
237
views
Sequences for which $\prod (1-z^n)^{a(n)}$ is a polynomial
This is mostly a reference request.
I'm working with complex coefficients, although all I have in mind have integer coefficients.
Let $a=(a(n))_{n\ge 1}$ be a sequence, say of integers (I have non-...
- 63.9k
8
votes
0
answers
145
views
Minimum length of sequence such that every integer from 1 to n can be achieved as the sum of some contiguous subsequence
This question literally came to me in a fever dream last night, and it's frustrating me to no end. I'll try to explain it as best I can, but there may not be a satisfying answer; the best outcome ...
7
votes
0
answers
184
views
Some conjectural congruences involving Domb numbers
The Domb numbers are given by
$$D_n=\sum_{k=0}^n\binom{n}{k}^2\binom{2k}k\binom{2(n-k)}{n-k}\ \ \ (n=0,1,2,\ldots).$$
Such numbers have combinatorial interpretation, see, e.g., http://oeis.org/A002895....
- 15.6k
7
votes
0
answers
945
views
Intuition behind salient numbers in number of h-cobordism classes of smooth homotopy n-spheres
The Wikipedia article on Exotic Sphere displays this sequence of numbers (see also OEIS A001676 and the Milnor link therein) for the order of the classses as
$$1, \;1, \;1,\; 1,\; 1, \;1, \;28,\; 2,\; ...
- 10.5k
6
votes
0
answers
171
views
An inequality involving integer partitions
For integers $n\ge k\ge0$, let $p(n,k)$ denote the number of ways to write $n$ as a sum of $k$ positive integers (repetition allowed). For example, $p(6,3)=3$ since
$$6=1+1+4=1+2+3=2+2+2.$$
QUESTION. ...
- 15.6k
6
votes
0
answers
245
views
Searching for a proof of the pattern and identification of integer coefficients for the A329369
Please see the update given below. Everything you need to know from the old version of the question are the functions $a(n), \ell(n), s(n), t(n), r(n)$.
Let $a(n)$ be A329369 (i.e, number of ...
- 4,948
6
votes
0
answers
286
views
Does $a_{i}(n)$ hit every positive integers infinitely many times for all $i\ge1$?
This question is related to a family of sequences. I have a simple definition as below and I have a question based on my limited observations for $i\le200$ and $n \le 10^{9}$.
Definition. $a_{i}(1) = ...
- 701
6
votes
0
answers
284
views
Is there a positive odd $n$ such that $\sigma(\sigma(n)) = \sigma(\sigma(n)-n)+\sigma(n)$?
Let $\sigma(n)$ denote the sum of the divisors of $n$. (https://oeis.org/A000203)
It is relatively easy to find numbers $n$ such that $f(g(n)) = g(f(n))$ where $f(n) = \sigma(n)$ and $g(n) = \sigma(n) ...
- 701
6
votes
0
answers
207
views
When is the ratio of Jacobi theta functions algebraic?
Probably this is well known.
$\theta_2$ and $\theta_3$ are Jacobi theta functions
as defined in mathworld (31) and (32).
For natural $n$ define
$$ f(n) = \frac{\theta_2(-e^{-\pi\sqrt{n}})}{\theta_3(-e^...
- 25.4k
5
votes
0
answers
307
views
On $s$-additive sequences
For a non-negative integer $s$, a strictly increasing sequence of positive integers $\{a_n\}$ is called $s$-additive if for $n>2s$, $a_n$ is the least integer exceeding $a_{n-1}$ which has ...
- 791
5
votes
0
answers
133
views
Formula and smallest solution for the A260711
Let $a(n)$ be A260711 without initial $0$ (i.e., numbers of the form $x^2 - y^2$ with $x > y$ where $x$ and $y$ are odd, $x + y$ is a power of $2$).
The sequence begins with
$$
8, 16, 32, 48, 64, ...
- 4,948
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 ...
- 341
5
votes
0
answers
317
views
Elliptic curve sequences needed for universal forgery
Elliptic Curve Digital Signature Algorithm (ECDSA) admits universal forgery (UF) if the Attacker can solve the equation
$$z=\frac{f_{k-1}(x,y)f_{k+1}(x,y)}{f_{k}(x,y)^2},$$
where $k$ is unknown, $f_{k}...
- 12.3k
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 ...
- 19.6k
4
votes
0
answers
121
views
Do all nonnegative integers appear in A051521?
For every positive integer $n$, $\tau(n)$ is the number of divisors of $n$. If we list the ratio of each positive integer $n$ to $\tau(n)$，they form a rational sequence
1,1,3/2,4/3,5/2,3/2,…
Because $\...
- 321
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 ...
- 141
4
votes
0
answers
414
views
Explicit formula for tournament sequence
I am looking for an explicit formula for a sequence. The sequence is generated as follows:
There is a tournament with $10$ teams. In the beginning, all teams have a 0-0 win-loss record. The teams are ...
- 41
4
votes
0
answers
300
views
On $\sum_{k=1}^nk^3 = x^3 + y^3$ with $x,y \ge 1$
My question is related to https://oeis.org/A269839.
It is well-known that there are parametric families of solutions for cubes that are sums of consecutive cubes: https://arxiv.org/pdf/1603.08901.pdf. ...
- 701
4
votes
0
answers
97
views
When is $\lfloor C^n \rfloor \mod b$ efficiently computable?
For real irrational $C > 1 $ and natural $n,b$, define
$a(C,n,b)=\lfloor C^n \rfloor \mod b$
Q1 For which $C,b$ is $a(C,n,b)$ computable in time polynomial
in $\log{n}$?
Searching in OEIS ...
- 25.4k
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{...
- 15.6k
4
votes
0
answers
206
views
Generating a Penrose tessellation around a given tile
Given a starting Penrose tile, I need to build a "spiraling" tessellation around it.
The following picture illustrates the request:
In this example, the starting tile is a "thin rhombus" (the pink ...
- 145
3
votes
0
answers
128
views
Fast and simple algorithm for the A329369
Let $a(n)$ be A329369 (i.e., number of permutations of $\{1,2,\cdots,m\}$ with excedance set constructed by taking $m-i$ ($0 < i < m$) if $b(i-1) = 1$ where $b(k)b(k-1)\cdots b(1)b(0)$ ($0 \...
- 4,948
3
votes
0
answers
120
views
Sequence which is related to the binary expansion of $n$ and partition numbers
Let $p(n)$ be A000041 i.e. the number of partitions of $n$ (the partition numbers).
Let
$$
\ell(n)=\left\lfloor\log_2 n\right\rfloor
$$
Let $\operatorname{wt}(n)$ be A000120 i.e. number of $1$'s in ...
- 4,948
3
votes
0
answers
69
views
Sequence that sum up to A343685
Let $a(n)$ be A343685 i.e.
$$
a(n)=2na(n-1)+\sum\limits_{j=0}^{n-1}\binom{n}{j}(n-j-1)!a(j), \\
a(0)=1
$$
Here the exponential generating function $A(x)$ satisfy
$$
A(x)=\frac{1}{1-2x+\log(1-x)}
$$
...
- 4,948
3
votes
0
answers
165
views
Closed form for $a(2^m(2^n-2^p-1))$
Let $q(n)$ be A007814, i.e., the number of trailing zeros in the binary representation of $n$. Here
$$q(2n+1)=0, q(2n)=q(n)+1$$
Let $a(n)$ be A329369. Here
$$a(2n+1)=a(n), a(2n)=a(n)+a(n-2^{q(n)})+a(...
- 4,948
3
votes
0
answers
195
views
3
votes
0
answers
285
views
Catalan numbers, Pochhammer symbols, Stirling numbers of the second kind, and sums of aliquot parts
For integers $N\geq 1$ we define $$s(N)=\sigma(N)-N$$ the aliquot sum function, where $\sigma(N)=\sum_{1\leq d|N}d$ is the sum of divisors function.
Here $(x)_n$ is the Pochhammer symbol and ${a\...
3
votes
0
answers
180
views
Additive combinatorics and a Diophantine equation
Let $(n_k)_{1 \leq k \leq N}$ be a sequence of distinct positive integers. For $v \in \mathbb{Z}$ set
$$
A_N(v) = \# \Big\{ (k,\ell) \in \{1, \dots, N\}^2, ~k \neq \ell:\quad n_k - n_\ell = v \Big\}.
$...
- 2,227
3
votes
0
answers
86
views
Increasing integral sequence of intermediate growth which is periodic modulo almost all primes
Many integral sequences are periodic modulo (almost) all primes.
However all examples I know are either evaluations of suitable polynomials on consecutive integers (trivial examples) or grow at least ...
- 17.9k
3
votes
0
answers
100
views
Searching information on a certain function with a fixed point property connecting Moebius $\mu$ and Fibonacci numbers
Let $\mu$ be the Moebius function and define for $1\leq n\in\mathbb{N}$
$$
f(n) =
\left\{
\begin{array}{ll}
\mu\left(\frac{n}{2}\right) + \mu\left(\frac{n}{4}\right), & n\equiv 0, 4, 8\mod 12, \\
...
- 410
3
votes
0
answers
252
views
What are the values of this sequence?
Let $F_n$ denote the $n$th Fibonacci number.
Then $\prod\limits_{i=1}^{\infty}(1-x^{F_i})$ is a series all of whose coefficients are either $-1$, $0$ or $+1$.
The sequence of the coefficients in ...
- 2,143
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 ...
2
votes
0
answers
62
views
Algorithm for main diagonal of integer coefficients associated with Schroeder numbers
Let $T_q(n, k)$ be an integer table such that
$$T_q(n, k) = \begin{cases}
1 & \textrm{if } n = 0 \vee k = 0 \\
qT_q(n-1, n-1) + T_q(n, n-1) & \textrm{if } n = k > 0 \\
T_q(n, k-1) + T_q(n-1,...
- 4,948
2
votes
0
answers
28
views
On doubling or addition formulas for the sequence $a(n)=(b_1 n +b_2)a(n-1)+(b_3 n + b_4)a(n-2)$
We are interested which integer sequences are efficiently computable
possibly over finite rings.
Define the integer sequence $a(n)=(b_1 n +b_2)a(n-1)+(b_3 n + b_4)a(n-2)$
with initial terms $a(0),a(1)$...
- 25.4k
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 ...
- 25.4k
2
votes
0
answers
110
views
bijection from vectors with non-negative integer integer entries to integers
I have the following question. Given a natural number $N$ we construct a set $K$ of vectors of infinite length with non-negative integer entries with a given sum $N$. For example, for $N=3$ the set $K$...
- 61
2
votes
0
answers
163
views
Interesting conjecture by Sequence Machine
Let $a(n)$ be A344960 (i.e., position of binary complement of $n$-th word in A341258). By definition, in order to calculate $a(n)$, we need to know A341258. Below we will correspond this sequence with ...
- 4,948
2
votes
0
answers
72
views
Possible subsequence of the A110978
Let $a(n)$ be A110978 i.e. odd integers that are nonprime, such that there exist two factors of each number that when multiplied together in binary base, do not ever require the use of a "carry&...
- 4,948
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$...
- 4,948
2
votes
0
answers
126
views
Recurrence for A004208
Let $a(n)$ be A004208. Here
$$a(n)=n\prod\limits_{j=1}^{n}(2j-1)-\sum\limits_{i=1}^{n-1}a(i)\prod\limits_{j=1}^{n-i}(2j-1)$$
I conjecture that
$$a(n)=R(n-1,0)$$
where
$$R(n,q)=2(q+2)R(n-1,q+1)+\sum\...
- 4,948
2
votes
0
answers
105
views
Sequences that sum up to the many sequences in the OEIS
Let
$$a(n,m,k)=\frac{1}{n}\sum\limits_{j=0}^{n}[n+kj\geqslant 0]\binom{n}{j}\binom{n+kj}{j-1}(m-1)^{j-1}$$
Here square brackets denote Iverson brackets.
There are many sequences in the OEIS that are ...
- 4,948
2
votes
0
answers
70
views
Integer coefficients such that $T(n,k)=R(n,k)-R(n,k-1)$
Let $a(n)$ be A000085, i.e., the number of self-inverse permutations on $n$ letters, also known as involutions; number of standard Young tableaux with $n$ cells. Here
$$a(n) = a(n-1) + (n-1)a(n-2), a(...
- 4,948
2
votes
0
answers
76
views
Uniqueness of the permutation
Let $f(n)$ be A000045(n), i.e., Fibonacci numbers: $f(n)=f(n-1)+f(n-2)$ for $n>1$ with $f(0)=0$ and $f(1)=1$.
Let $g(n)$ be A072649, i.e., $n$ occurs $f(n)$ times. The sequence begins with
$$1, 2, ...
- 4,948