Question

HELP!!!
http://prntscr.com/4cpnbs

Answer 1

767, 76767, 7676767, 76767676767...

Answer 2

that's a covering set,right? @rational

Answer 3

we need to prove all the numbers of above form are not prime

Answer 4

but they are set of prime numbers..... :O

Answer 5

@satellite73 @ganeshie8

Answer 6

@Mokeira

Answer 7

http://math.stackexchange.com/questions/896733/factoring-numbers
i think u'll get some idea from this

Answer 8

thanks! i got this problem from there itself :) they couldn't solve this in that site

Answer 9

still i am so confused @sidsiddhartha

Answer 10

yeah mee too i'm really very bad with number theory :(

Answer 11

these numbers can be representd as :

\[\large 7*10^{2k} + 67(10^{2k-2} + 10^{2k-4}+ \cdots 10^0)\]
\(k \ge 1\)

Answer 12

i think @ganeshie8 can help u with this

Answer 13

we need to show that this expression can always be factored or something, no idea how to proceed further

Answer 14

better tag few more guys here.......!!!

Answer 15

Let's look at how the method works for the example sequence.

The sequence an is generated by the recurrence an+1=100an+67. Applying this three times, we get:

an+3=100(100(100an+67)+67)+67=106an+676767
(Which really we could also have realized intuitively) The prime factors of 676767 are 3,7,13,37 and 67, and it so happens that each of a0,a1 and a2 are divisible by one of those numbers. This is enough to start an induction showing what's asked in the problem statement. Indeed, if an is divisible by a prime factor of 676767, then 106an+676767 is clearly also divisible by it.

Set up a similar recurrence relation for the other problems. Note that in the example problem, the choice of 3 (you look at the effect of applying the recurrence function 3 times) is somewhat arbitrary - it just happens to work. There's no guarantee that 3 will work for the other examples. So look at what happens when you apply the recurrence k times. You'll get a relation of the form:

an+k=102kan+c
You'll need a k such that the numbers a0,a1,...ak−1 all have common factors with c. Note that of course both c and the ai will have very specific, easily predictable forms, which might help the analysis.

Answer 16

i just copy pasted that...lol

Answer 17

lol.. i am more confused after reading that.......!
still no solution?? @rational

Answer 18

@tejasvir @Abhisar need your help here!!!!!!

Answer 19

a composite number is an number that isn't prime and can be divided by numbers other than one and itself..

Answer 20

that was easy problem :P

Answer 21

That's it?

Answer 22

well this is how its going for 767
\[\large a_0 =7\\
\large a_{n+1}=100 a_n+67\\

\begin{matrix}
a_1=767& a_2=76767 & a_3=7676767 \\
a_4=767676767 & a_5=76767676767 & a_6=7676767676767 \\
a_7=767676767676767 & a_8=76767676767676767 & a_9=7676767676767676767 \\
... & ... & ... \\
a_{3n+1}=10^6 (a_{3(n-1)+1})+676767 & a_{3n+2}=10^6 (a_{3(n-1)+2})+676767 &a_{3n+3}=10^6 (a_{3(n-1)+3})+676767

\end{matrix}
\]
http://prntscr.com/4cu2ju

but 6767=3*13*7k
and you would note that

\( a_1=0 \mod 13\\a_4 \mod 13=10^6 a_1 +6767 \mod 13= a_1 \mod 13 \)
keep going with this, then you would get a battern
\(\large a_1 \mod 13 =a_4 \mod 13 =a_7 \mod 13 =...=a_{3n+1} \mod 13 =0 \)

same thing with \(a_2, a_3\)
\(\large a_2 \mod 3 =a_5 \mod 3 =a_8 \mod 3 =...=a_{3n+2} \mod 3 =0 \)
\(\large a_3 \mod 7 =a_6 \mod 7 =a_9 \mod 7 =...=a_{3n+3} \mod 7 =0 \)

Answer 23

brilliant ! got it now xD

Answer 24

1 down, still two more to go !

Answer 25

prime factorization for first few terms of second sequence :

\[\large \begin{array}\\
343 &: 7^3\\
34343 &: 61\times 563\\
3434343 &: 3\times 11^2\times 9461\\
343434343 &: 7\times 521\times 94169\\
34343434343 &: 47\times 79\times 9249511\\
3434343434343 &: 3^2\times 19\times 29\times 67\times10336531\\
343434343434343 &: 7\times 151\times 324914232199\\
34343434343434343 &: 5638147\times 6091262669
\\
\end{array}\]

it seems the earlier method wont work here as there is no pattern and the prime numbers are getting really bigger...

Answer 26

wait a sec, there seems to be some pattern for `7` and `3` :

\[\large \begin{array}\\
\color{Red}{343} &\color{Red}{: 7^3}\\
34343 &: 61\times 563\\
\color{green}{3434343} &\color{green}{: 3\times 11^2\times 9461}\\
\color{red}{343434343} &\color{Red}{: 7\times 521\times 94169}\\
34343434343 &: 47\times 79\times 9249511\\
\color{green}{3434343434343} &\color{green}{: 3^2\times 19\times 29\times 67\times10336531}\\
\color{red}{343434343434343} &\color{Red}{: 7\times 151\times 324914232199}\\
34343434343434343 &: 5638147\times 6091262669
\\
\end{array}\]

Answer 27

can we say :
\(\large a_{3k} \equiv 0 \mod 7\)
\(\large a_{3k+2} \equiv 0 \mod 3\)

?

Answer 28

\(\large a_{3k+1}\) is looking nasty

Answer 29

thats it, \(\large a_{3k+1}\) seems to diverge, so we may not be able to prove they are composite using the earlier method. give up :)

Answer 30

# its not you who give up .

both other sequenses the same to the first one :-
434343=3*7*13*37*43

\[\large a_0 =3\\
\large a_{n+1}=100 a_n+43\\

\begin{matrix}
a_1=343& a_2=34343 & a_3=3434343 \\
a_4=343434343 & a_5=34343434343 & a_6=3434343434343 \\
a_7=343434343434343 & a_8=34343434343434343 & a_9=3434343434343434343 \\
... & ... & ... \\
a_{3n+1}=10^6 (a_{3(n-1)+1})+434343 & a_{3n+2}=10^6 (a_{3(n-1)+2})+434343 &a_{3n+3}=10^6 (a_{3(n-1)+3})+434343

\end{matrix}
\]
http://prntscr.com/4cxf12


\( a_1=0 \mod 7\\a_4 \mod 13=10^6 a_1 +4343 \mod 7= a_1 \mod 7\)
keep going with this, then you would get a battern
\(\large a_1 \mod 7 =a_4 \mod 7 =a_7 \mod 13 =...=a_{3n+1} \mod 7 =0 \)

same thing with \(a_2, a_3\)
\(\large a_2 \mod 13 =a_5 \mod 13 =a_8 \mod 13 =...=a_{3n+2} \mod 13 =0 \)
\(\large a_3 \mod 3 =a_6 \mod 3 =a_9 \mod 3 =...=a_{3n+3} \mod 3 =0 \)

Answer 31

i copied the same latex :P

the trick in last line
http://prntscr.com/4cxg5g

once u got the nested relation then mod will only depand on \(a_1,a_2 ,a_3\) factors

common factors with 434343 will be the battern

Answer 32

same thing with 7171...
wanna try ?

Answer 33

wait, i don't get 3434343 yet

Answer 34

:o
which part you dint get ?

Answer 35

i was going through the third one :P
ok i will explain

Answer 36

whats your explanation for the number `34343` ?

Answer 37

it is divisible by 7 or 3, right ?

Answer 38

3, 7,13

Answer 39

ok , u got this part ?
http://prntscr.com/4cxnlu

ill make you understand it from here

Answer 40

yes and factors of 434343 are `3,7,13,37,43`

however the second term : 34343 = 62x563 has no shared factors with above^^ so we cannot use ur argument

Answer 41

its ovs that when u go through it , it will be like this
( will solve for first one )

\(a_4= 10 ^6 a_1 +434343\)
\(a_7= 10 ^6 a_4 +434343\)
\(a_10= 10 ^6 a_7 +434343\)
\(a_13= 10 ^6 a_10 +434343\)

Answer 42

how on earth
34343 = 62x563 !

Answer 43

not its odd number

Answer 44

note*

Answer 45

oh now i got what u mean lol sorry

Answer 46

i dint note that before hehe im strugeling with 3k+2 it :P
its my fault i dint try it hehe

Answer 47

exactly! to argue \(a_4= 10 ^6 a_1 +434343\) is composite you need to show that \(a_1\) and \(434343\) have a common factor

Answer 48

yeah , but seems with 34343434 and 171717 we have problem with a_(3k+2) case

Answer 49

yes, this method wont work

Answer 50

i need to sleep hehe then will figure out

Answer 51

Ohh I thought you woke up just now lol

Answer 52

there is absolutely no rush, #2 and #3 are really tough ! try them in your free time :) gnite!

Answer 53

good morning :P