All Questions
Tagged with integer-sequences nt.number-theory
241 questions
69
votes
1
answer
4k
views
Iterations of $2^{n-1}+5$: the strong law of small numbers, or something bigger?
I've discovered what I believe is a quite remarkable sequence (A318970), defined by
$$n_1 = 3,\qquad n_{k+1} = 2^{n_k-1}+5\quad(k\geq 1).$$
Here are the first four terms with their prime ...
- 34.4k
49
votes
4
answers
4k
views
Strange (or stupid) arithmetic derivation
Let us consider the following operation on positive integers: $$n=\prod_{i=1}^{k}p_i^{\alpha_i} \qquad f(n):= \prod_{i=1}^{k}\alpha_ip_i^{\alpha_i-1}$$ (Is it true that if we apply this operation to ...
- 3,004
41
votes
1
answer
1k
views
Mod sequences that seem to become constant; and the number 316
Define a "mod sequence" of nonnegative integers
based on one start parameter $s$, its first term,
as follows.
$A(s)=(a_1,a_2,\ldots,a_n,\ldots)$
with $a_1 = s$
and
$$ a_n = \left(\sum_{k=1}^{n-1} a_k \...
- 151k
35
votes
8
answers
3k
views
Examples of integer sequences coincidences
For the time being, the OEIS website contains almost $300000$ sequences. Each of these sequences is the mark of a specific mathematical concept. Sometimes two (or more) distinct concepts have the ...
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
34
votes
1
answer
3k
views
A remarkable almost-identity
OEIS sequence A210247 gives the signs of $\text{li}(-n,-1/3) = \sum_{k=1}^\infty (-1)^k k^n/3^k$, also the signs of the Maclaurin coefficients of $4/(3 + \exp(4x))$.
Mikhail Kurkov noticed that it ...
- 54.2k
33
votes
2
answers
856
views
A sequence potentially consisting of only integers
I will first ask the question which can be stated very simply. Afterwards I will explain some motivation and give references to related sequences.
Consider the sequence defined by
$$b_n = \frac{(...
- 7,875
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
26
votes
1
answer
7k
views
Elegant recursion for A301897
Let $a(n)$ be A301897, i.e., number of permutations $b$ of length $n$ that satisfy the Diaconis-Graham inequality $I_n(b) + EX_n(b) \leqslant D_n(b)$ with equality. Here
$$a(n)=\frac{1}{n+1}\binom{2n}{...
- 4,948
26
votes
1
answer
3k
views
A surprising conjecture about twin primes
Just for fun, I began to play with numbers of two distinct ciphers. I noticed that most of the cases if you consider the numbers $AB$ and $BA$ (written in base $10$), these have few common divisors: ...
- 363
24
votes
1
answer
2k
views
Parity of the multiplicative order of 2 modulo p
Let $\operatorname{ord}_p(2)$ be the order of 2 in the multiplicative group modulo $p$. Let $A$ be the subset of primes $p$ where $\operatorname{ord}_p(2)$ is odd, and let $B$ be the subset of primes $...
- 429
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
23
votes
5
answers
1k
views
Sequences with integral means
Let $S(n)$ be the sequence whose first element is $n$, and from then onward,
the next element is the smallest natural number ${\ge}1$ that ensures that the
mean of all the numbers in the sequence is ...
- 151k
20
votes
2
answers
1k
views
A possibly surprising appearance of $\sqrt{2}.$
Define $A=(a_n)$ and $B=(b_n)$ as follows: $a_0=1$, $a_1=2$, $b_0=3$, $b_1=4$, and $$a_n=a_1b_{n-1}-a_0b_{n-2} + 2n$$ for $n \geq 2$, where $A$ and $B$ are increasing and every positive integer occurs ...
- 3,443
19
votes
1
answer
1k
views
Is every sequence that looks like an AP really an AP?
Caveat: I am not at all a number theorist, and I randomly came up with the following question while I was hiking. But I already asked two serious number theorists, and since they did not know the ...
- 11.9k
19
votes
1
answer
1k
views
Is OEIS A007018 really a subsequence of squarefree numbers?
A comment in A007018 a(n) = a(n-1)^2 + a(n-1), a(0)=1 claims
Subsequence of squarefree numbers (A005117). - Reinhard Zumkeller, Nov 15 2004
Is that really so?
As far as I know, it is an open ...
- 25.4k
18
votes
2
answers
992
views
A conjecture harmonic numbers
I will outlay a few observations applying to the harmonic numbers that may be interesting to prove (if it hasn't already been proven).
From the Online Encyclopedia of Positive Integers we have:
$a(n)$ ...
- 181
17
votes
2
answers
3k
views
Some unpublished notes of Hofstadter
I'm looking for some unpublished notes called "Eta Lore," which are apparently related to a talk Douglas Hofstadter first gave at the Stanford Math Club in 1963. I know these notes exist because they'...
16
votes
2
answers
1k
views
are these polynomials or rationals functions?
Let $x$ be a variable. Define the following family of sequences (reminiscent of Lucas polynomials) according to the rule: $P_0(x):=0, P_1(x):=1$ and for $n\geq2$ by
$$P_n(x)=xP_{n-1}(x)-P_{n-2}(x).$$
...
- 43.2k
15
votes
1
answer
475
views
Determinant of a matrix filled with elements of the Thue–Morse sequence
Let $n$ be a positive integer. Suppose we fill a square matrix $n\times n$ row-by-row with the first $n^2$ elements of the Thue–Morse sequence (with indexes from $0$ to $n^2-1$). Let $\mathcal D_n$ be ...
- 6,829
15
votes
1
answer
2k
views
Conjecture on signed sum of integer fractions x/y from 1..N?
Here is a generalization of an integer challenge that was asked on Yahoo!Answers in 2009, I believe it could be original, defies induction and has exponential-complexity. Not aware of any theory that ...
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
14
votes
5
answers
977
views
Is the sequence $a_n=c a_{n-1} - a_{n-2}$ always composite for $n > 5$?
Numerical evidence suggests the following.
For $c \in \mathbb{N}, c > 2$ define the sequence $a_n$ by
$a_0=0,a_1=1, \; a_n=c a_{n-1} - a_{n-2}$
For $ 5 < n < 500, \; 2 < c < 100$ there ...
- 25.4k
14
votes
1
answer
835
views
Special configurations on a circle from a homological algebra problem
Here is the short version of the combinatorial problem:
Given a positive integer $n \geq 2$. Draw a circle with $2n$ points indexed by the numbers from $\mathbb{Z}/ 2n \mathbb{Z}$. We colour the ...
- 26.5k
13
votes
2
answers
2k
views
Positive integers written as $\binom{w}2+\binom{x}4+\binom{y}6+\binom{z}8$ with $w,x,y,z\in\{2,3,\ldots\}$
Let $\mathbb N=\{0,1,2,\ldots\}$. Recall that the triangular numbers are those natural numbers
$$T_x=\frac {x(x+1)}2\quad \text{with}\ x\in\mathbb N.$$
As $T_x=\binom{x+1}2$, Gauss' triangular number ...
- 15.6k
13
votes
1
answer
700
views
When is $\mathrm{gcd}(k,p^k-1)=1$ true?
Let $p$ be a prime. Is there a classification of the numbers $k \geq 1$ such that $\gcd(k,p^k-1)=1$? If not, can we at least produce an explicit infinite subset? What is known about these $k$?
For the ...
- 63.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
12
votes
4
answers
1k
views
Six consecutive positive integers with certain shape
Are there 6 consecutive positive integers, where each of them is a square or the product of a prime and a square ?
If they exist, one of those six integers A will be the product of 2 and a square of ...
- 321
12
votes
1
answer
427
views
Subwords of the infinite Fibonacci word
Let $W = 01001010010010 \ldots$ be the infinite Fibonacci word, A003849 in the OEIS. Let $B(m)$ be the set of $m+1$ subwords of $W$ that have length $m$, and for each such subword $u$, let $p(u)$ be ...
- 479
11
votes
1
answer
864
views
Up to $10^6$: $\sigma(8n+1) \mod 4 = OEIS A001935(n) \mod 4$ (Number of partitions with no even part repeated )
Up to $10^6$:
$\sigma(8n+1) \mod 4 = OEIS A001935(n) \mod 4$
A001935 Number of partitions with no even part repeated
Is this true in general?
It would mean relation between restricted partitions ...
- 25.4k
10
votes
2
answers
1k
views
Consecutive numbers with mutually distinct exponents in their canonical prime factorization
Is it possible to find 23 consecutive positive integers each of which has mutually distinct exponents in its canonical prime factorization? Such numbers are sequence A130091 in OEIS. 24 such numbers ...
- 3,717
10
votes
1
answer
589
views
XOR-free sets: Maximum density?
It is known that sum-free
subsets of $\mathbb{N}$ can have
natural density at most
$\frac{1}{2}$. This density is achieved by the odd numbers: the sum of two
odd numbers is even.
I ask now a similar ...
- 151k
10
votes
2
answers
735
views
A number sequence problem involving binomial transform
Let $\{b_n\}_{n\geq0}$ be a sequence such that $b_nb_{n+1}=0$ and define
$$a_n:=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}b_k.$$
If $\lim_{n\to\infty}a_n=0$, can we conclude that $b_n=0$ for all $n$?
More ...
- 111
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
9
votes
2
answers
546
views
Can you tie up these Laurent sequences?
Fix an integer $k\geq3$. Define the two families of sequences $\{x_n\}$ and $\{y_n\}$ according to the rules:
$$x_n=\frac{x_{n-1}^2+x_{n-2}^2+\cdots+x_{n-k+1}^2}{x_{n-k}} \qquad n\geq k$$
and
$$y_n=\...
- 43.2k
9
votes
2
answers
1k
views
The p-adic valuation of a linear recurrence
Let $(u_n)_{n \geq 0}$ be an integer-valued linear recurrence of order $k \geq 1$. Precisely,
$$u_n = a_1 u_{n-1} + \cdots + a_k u_{n - k} \quad \forall n \geq k ,$$
for some $a_1, \ldots, a_k \in \...
user40023
8
votes
1
answer
568
views
Arbitrarily many primes in a Fibonacci-type sequence
It is conjectured that the standard Fibonacci sequence contains infinitely many primes. While this is perhaps too difficult, I am wondering about the following simpler version:
Question. For any $K$, ...
- 765
8
votes
1
answer
364
views
Is the permanent of the matrix $[(\frac{i+j}{2n+1})]_{0\le i,j\le n}$ always positive?
Recall that the permanent of an $n\times n$ matrix $A=[a_{i,j}]_{1\le i,j\le n}$ is defined by
$$\operatorname{per}A=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.$$
In 2004, R. Chapman [Acta ...
- 15.6k
8
votes
1
answer
363
views
Possible small mistake in Bilu-Hanrot-Voutier paper on primitive divisors of Lehmer sequences (?)
I think that I might have spotted I small mistake (a missing $5$-defective Lehmer pair) in the classification of terms of Lehmer sequences without primitive divisors given in:
1 Bilu, Hanrot, and ...
- 65
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
4
answers
1k
views
Find a formula for the recurrent sequence $q_{n+1}=q_n(q_n+1)+1$
Find an analytic formula for the recurrent sequence $$q_{n+1}=q_n(q_n+1)+1,\;\;q_0\in\mathbb N.$$
(The question was asked on 03.05.2018 by M. Pratsovytyi, see page 109 of Volume 1 of the Lviv ...
- 4,535
7
votes
2
answers
428
views
Limit associated with complementary sequences
Define $A=(a_n)$ and $B=(b_n)$ as follows: $a_0=1$, $a_1=2$, $b_0=3$, $b_1=4$, and $$a_n=a_0b_{n-1}+a_1b_{n-2}$$ for $n \geq 2$, where $A$ and $B$ are increasing and every positive integer occurs ...
- 3,443
7
votes
1
answer
527
views
Suitable closed form for the A079501
Let $a(n)$ be A079501 (i.e., number of compositions of the integer $n$ with strictly smallest part in the first position).
The sequence begins with
$$
1, 1, 2, 2, 4, 5, 8, 12, 19, 28, 45, 70, 110, ...
- 4,948
7
votes
1
answer
283
views
On one class of Somos-like sequences
This question is motivated by integrability of the sequence mistakenly arisen in the question Does this sequence always give an integer?
Let $m_1,\ldots, m_{k-1}$ be positive integers and sequence $\{...
- 12.3k
7
votes
1
answer
286
views
On nontotient Fibonacci numbers
This question is related to sequence of numbers $t$ such that $F_{6t}$ is a nontotient where $F_n$ represents the sequence of Fibonacci numbers for $n\geq 0$.
The online encyclopedia Wikipedia has the ...
- 701
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
5
answers
546
views
Bounds for $a(n)=a(n-1)+a(\lfloor n/2 \rfloor)$
This is related to problem in graph theory.
OEIS defines A033485 as
$a(1)=1$ and $a(n)=a(n-1)+a(\lfloor n/2 \rfloor)$.
Q1 what are upper bounds and asymptotics for $a(n)$, can we get $\exp(o(n))$?
...
- 25.4k