Problems & Puzzles: Puzzles
|
Problems & Puzzles: Puzzles
From Oct 11-17, 2025, contributions came from Ivan Ianakev, Emmanuel Vantieghem, Michael Branicky, Adam Stinchcombe, Gennady Gusev, Adam Stinchcombe *** I van wrote:
The proof is very simple if we start with Jon Perry's observation at
A000212 (dated Sep 10 2012).
After a case analysis we see that:
1. If n is congruent to 0 mod 3, then 3 divides a(n);
2. If n is not congruent to 0 mod 3, then (y-1)(y+1) is divisible by 2
or 3, so a(n) is composite again.
*** Emmanuel wrote:
Proof.
Let F(n) = Floor(n^2 / 3).
When n = 3k then F(n) = 3k^2, composite when k > 1.
When n = 3k + 1 then F(n) = Floor(3k^2 + 2k + 1/3) = 3k^2 + 2k,
composite when k > 1 .
When n = 3k + 2 then F(n) = Floor(3k^2 + 4k + 1 + 1/3) = (k + 1)(3k +
1), composite for k >= 1.
Thus, F(n) is composite for n > 4, QED.
*** Michael wrote: I first quickly checked that there were no counterexamples 4 < n <= 10^9 using computer search (~6 min). Then, I turned to proof. It is easy to prove the statement is true by reasoning over the three cases for n mod 3. Indeed, a Google search on [prove that Floor[n^2/3] is composite for all n>4] quickly proved this, which I checked, finding no flaw. A screenshot of its proof attached. (NB by CR: the proof is similar to the sent by Emmanuel and others) **** Adam wrote: You can prove this on a case by case basis. If n=3k then n^2/3 = (3k)^2/3 = 3k^2 which is composite for k>1. If n=3k+1, n^2/3 = (3k+1)^2/3 = (9k^2+6k+1)/3 = 3k^2 + 2k + 1/3 which has a floor of 3k^2+2k = k(3k+2) which is composite for k>1. Finally, if n=3k+2, n^2/3 = (9k^2 +12k + 4)/3 = 3k^2 +4k +4/3 which has a floor of 3k^2 + 4k + 1 =(k+1)(3k+1) which is composite for k>=1. *** Gennady wrote:
Note that floor(integer+1/3)=integer.
Consider 3 cases for n.
1. n=3*k.
(3*k)^2/3=3*k^2. Composite for k=2,3,4.. -> n=6,9,12,...
2. n=3*k-1.
floor((3*k-1)^2/3)= (subtract 1 and add 1)
=floor(((3*k-1)^2-1+1)/3)=
Composite for k=2,3,4.. -> n=5,8,11...
3. n=3*k-2.
floor((3*k-2)^2/3)= (subtract 1 and add 1)
=floor(((3*k-2)^2-1+1)/3)=
Composite for k=3,4.. -> n=7,10,13...
Result: floor(n^2/3) is composite for all n>4.
*** Adam wrote:
Conjecture: for each sufficiently large D (maybe D>16) and for each A
there is an N>A such that floor(N^2/D) is prime. In other words, "all
composite" only happens for select few denominators.
My candidate D that have tail end all composite are {1,2,3,4,5,8,12,16}.
***
|
|||
|
|||
|
|||
