Problems & Puzzles: Puzzles

Puzzle 197. Always composite numbers?

Sequences of odd numbers that remain composite without any easily evident reason may be as attractive as primes.

Three well known examples are the sequences produced using the Sierpinski, the Riesel or the Brier numbers.

Less glamorous examples must be hidden here and there, for sure....

Very, recently while tackling the puzzle 195 (*), I faced one probably interesting example of that kind of sequences:
 

343
33433
3334333
333343333
...

Some facts about this sequence are:

  • The members of the sequence can be obtained by 3*(10^(2*k+1)-1)/9+10^k, for k=1, 2, 3, ...
  • The rate of growth (quantity of additional digits from one member of the sequence to the next one) is 2.
  • According to  my old PRIMEFORM , these numbers remain composite up at least up to k=14000.

 

Questions:

1. Can you demonstrate that the members of that sequence are always composite, or can you find the first (probable) prime of them?

2. Can you report other interesting/beauty apparently always composite odd sequences ? (we prefer sequences with more number of members composites than the reported one above; this implicitly means a not very high rate of growth)

_____
* every member of this sequence is such that its square is a zero-free number

 

The Questions 1 & 2 of this puzzle was solved Ken Wilke, Jean Claude Rosa, Jim Howell, Jens Kruse Andersen and Faride FiroozBakht, basically the same way.

But only Patrick De Geest noticed that this question was posed and solved previously by Chris Caldwell and Harvey Dubner, in the Journal of Recreational Mathematics, Volume 28, Number 1, 1996-1997, pp. 1-9

Every term in our sequence is a composite of two factors according to the following pattern:

7 x 49 = 343
67 x 499 = 33433
667 x 4999 = 3334333
...
(6)k7 x 4(9)k = (3)k4(3)k , for k=>1

Other similar sequences of odd composites similar to the ours, and studied by Caldwell & Dubner, are:

(1)k0(1)k, for k>1

(1)k2(1)k, for k>0

(3)k2(3)k, for k>0

In particular Ken Wilke wrote:

Here is an answer to Question 1 of Problem 197. All members of the sequence are composite. In the proof I use Tk to denote the nth term (to avoid using subscripts).

Proof: Let Tk = 3*(10^(2*k+1)+1)/9 + 10^k. then since Tk is never divisible by 3 we have

3*Tk = Ak*Bk where Ak = 2*10^k+1 and Bk = 5*10^k-1. Since Both Ak and BK are greater than 3 for k = 1,2,..., and Ak is clearly divisible by 3, we have

Tk = (Ak/3)*Bk yielding the desired factorization of Tk.

Perhaps an interesting follow-up question would be: For what values of k are both (Ak/3) and Bk prime?

Faride FiroozBakht, wrote:

The members of the sequence f(k)=3*(10^(2*k+1)-1)/9+10^k, for every natural number k is always composite numbers. That is because:

f(k)=(5*10^k-1)*(6*(10^k-1)/9+1)=10/3*10^(2k)+10^k-1/3

***

J. C. Rosa has gotten a better example than the one I posed in this puzzle: 7(1)k7, for k=>0, seems to be always composite and seems to be free of a factorizing pattern as before...

In order to save some time, I would like to anticipate that 7(1)k7 is composite in the following general cases:

a) k=even; in this case 11 is a divisor
b) (k-1)@6=0; in this case 3 is a divisor
b) (k+1)@6=0; in this case 13 is a divisor

In short the only "interesting" cases to search for possible primes are when k=6m+3, for m=>0.

Can you try again with this sequence detecting or a prime or the reason why this is a composite number for any k?

***

J. K. Andersen solved the follow-up posed by J.C. Rosa. Here is his email:

There were apparently no pattern covering all numbers so I started
Primeform/GW and it relatively quickly found the smallest prp for k=10905:
7*10^(10905+1)+(10^10905-1)/9*10+7 is 3-PRP!. It is also prp in many other bases. A Miller-Rabin test from the Miracl big integer library also finds it a probable prime. It is too big to be proved with current methods.

Primeform/GW found no other prp's for k<27000 but I guess there are infinitely many primes in the sequence. I have not computed when the first should have been expected statistically. With all the patterns in prime factors, I am not so surprised that the smallest prp was gigantic.

***

 

 

 
Records   |  Conjectures  |  Problems  |  Puzzles