wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> divisibility by 29
        
(Message started by: Christine on Jul 22nd, 2013, 1:04pm)
Title: divisibility by 29
Post by Christine on Jul 22nd, 2013, 1:04pm
The rule is:
Add 3 times the last digit to the remaining truncated number. Repeat the step as necessary. If the result is divisible by 29, the original number is also divisible by 29

It's not practical with large numbers.
Is there a better way?

(2)
Take the number N = 131313....131
How many digits does N need in order to be divisible by 29?
Title: Re: divisibility by 29
Post by pex on Jul 22nd, 2013, 2:00pm

on 07/22/13 at 13:04:23, Christine wrote:
Take the number N = 131313....131
How many digits does N need in order to be divisible by 29?

28k+9, for k = 0,1,2,...
Title: Re: divisibility by 29
Post by Christine on Jul 22nd, 2013, 3:05pm
How do you establish this?


on 07/22/13 at 14:00:56, pex wrote:
28k+9, for k = 0,1,2,...


and the formulas for other primes other than 29, like 23, 31, etc.
Title: Re: divisibility by 29
Post by towr on Jul 22nd, 2013, 10:59pm
You use modular arithmetic. You only really need to know 10i mod p for i=0..p-2
For 29, we have that 13*sumi=0..13 102*i = 0 (mod 29), so you can just keep tacking on those 28 digits in front without changing the remainder modulo 29.
In general for repeating integers that repeats 2 digits (like 1313...131) and odd prime p > 11, you know you can tack on p-1 digits and get another integer with the same remainder. And all that left is how many digits to take from the right to get remainder 0.

d*sumi=0..(p-3)/2 102*i (mod p) = 99*sumi=0..(p-3)/2 100i (mod p)  = 10p-1 - 1 (mod p) = 0  (mod p)
(We can divide out d as long as p doesn't divide d, and if p does divide d it's 0 mod p anyway; similarly we can multiply by 99 because p > 11 won't divide 99)


In general you can do the following to test divisibility by k
start with m=1, s=0, then from the last digit on do the following for each:
 add m times the last digit to s and then remove the last digit
 multiply m by 10 and then set m to the remainder modulo k
(You might notice that for k=3 or k=9 this amounts to just adding all the digits, since m = 1 in each step)
Title: Re: divisibility by 29
Post by pex on Jul 23rd, 2013, 2:38am

on 07/22/13 at 15:05:30, Christine wrote:
How do you establish this?

Your sequence of numbers has N1 = 1, N2n+1 = 100N2n-1 + 31 (where the subscript is the number of digits, running through the odd positive integers only). Modulo 29, 100=13 and 31=2. I just iterated N2n+1 = 13N2n-1 + 2 (mod 29) to see where the first zero occurred and what the period of the cycle was - note that this sort of recursion has to end up in a cycle!
Title: Re: divisibility by 29
Post by Christine on Jul 24th, 2013, 7:18pm
The possible prime factors of 13131...1 are 3,11,17,29,43,61,67,71,97,103,109,131,149, 163,167,...  

I couldn't find any mention in OEIS.

Seems that about 1/3 of primes sometimes divide 1313..1.

Can we use modular arithmetic to find a pattern?
If there's, how?
Title: Re: divisibility by 29
Post by towr on Jul 24th, 2013, 11:28pm
Hmm, it appears to hold for all numbers abab..a ; they're always divisible by between 318 to 372 of the first 1000 primes
Title: Re: divisibility by 29
Post by Christine on Jul 26th, 2013, 1:39am

on 07/24/13 at 23:28:40, towr wrote:
Hmm, it appears to hold for all numbers abab..a ; they're always divisible by between 318 to 372 of the first 1000 primes


Not so. Try 7676...767
Title: Re: divisibility by 29
Post by towr on Jul 26th, 2013, 5:13am

on 07/26/13 at 01:39:29, Christine wrote:
Not so. Try 7676...767
They're divisible by 351 of the first 1000 primes, and with 351 laying between 318 and 372 I don't see how it's a counterexample.

Unless there's something wrong with my script..

Python
Code:
#x = <primelist>;
for i in range(11,100):
if i % 10 != 0:
 cnt = 0;
 for p in x:
  a = i % 10;
  for j in range(p):
   if a % p ==0:
    cnt+=1;
    break
   a = (100*a+i) % p;
 print((i%10)*100+i, '..', i, ': ' , cnt);



111 .. 11 :  325
212 .. 12 :  348
313 .. 13 :  343
414 .. 14 :  342
515 .. 15 :  351
616 .. 16 :  334
717 .. 17 :  341
818 .. 18 :  331
919 .. 19 :  360
121 .. 21 :  347
222 .. 22 :  326
323 .. 23 :  365
424 .. 24 :  348
525 .. 25 :  340
626 .. 26 :  344
727 .. 27 :  345
828 .. 28 :  342
929 .. 29 :  357
131 .. 31 :  343
232 .. 32 :  366
333 .. 33 :  325
434 .. 34 :  326
535 .. 35 :  355
636 .. 36 :  349
737 .. 37 :  358
838 .. 38 :  353
939 .. 39 :  343
141 .. 41 :  341
242 .. 42 :  348
343 .. 43 :  325
444 .. 44 :  326
545 .. 45 :  365
646 .. 46 :  366
747 .. 47 :  340
848 .. 48 :  348
949 .. 49 :  371
151 .. 51 :  350
252 .. 52 :  340
353 .. 53 :  354
454 .. 54 :  365
555 .. 55 :  326
656 .. 56 :  349
757 .. 57 :  355
858 .. 58 :  353
959 .. 59 :  318
161 .. 61 :  333
262 .. 62 :  344
363 .. 63 :  348
464 .. 64 :  366
565 .. 65 :  349
666 .. 66 :  326
767 .. 67 :  351
868 .. 68 :  326
969 .. 69 :  365
171 .. 71 :  341
272 .. 72 :  346
373 .. 73 :  358
474 .. 74 :  341
575 .. 75 :  356
676 .. 76 :  352
777 .. 77 :  326
878 .. 78 :  365
979 .. 79 :  367
181 .. 81 :  330
282 .. 82 :  342
383 .. 83 :  352
484 .. 84 :  348
585 .. 85 :  353
686 .. 86 :  326
787 .. 87 :  364
888 .. 88 :  326
989 .. 89 :  359
191 .. 91 :  360
292 .. 92 :  358
393 .. 93 :  343
494 .. 94 :  372
595 .. 95 :  319
696 .. 96 :  366
797 .. 97 :  367
898 .. 98 :  360
999 .. 99 :  325
Title: Re: divisibility by 29
Post by Christine on Jul 26th, 2013, 9:17am
I'm sorry towr, I was wrong.
Thank you for posting your list
Title: Re: divisibility by 29
Post by towr on Jul 26th, 2013, 12:51pm
Pretty much the same story up to 10000 primes (but it's a bit slower, so I only got to ..43 so far)
111..11: 3345
212..12: 3469
313..13: 3428
414..14: 3500
515..15: 3439
616..16: 3440
717..17: 3446
818..18: 3231
919..19: 3419
121..21: 3468
222..22: 3346
323..23: 3492
424..24: 3469
525..25: 3466
626..26: 3429
727..27: 3420
828..28: 3500
929..29: 3453
131..31: 3428
232..32: 3493
333..33: 3345
434..34: 3446
535..35: 3468
636..36: 3470
737..37: 3449
838..38: 3461
939..39: 3428
141..41: 3499
242..42: 3469
343..43: 3445
Title: Re: divisibility by 29
Post by Christine on Jul 26th, 2013, 4:29pm
Another question to ask not how many, but which primes divide abab...aba

I wonder if there's a necessary condition for a prime p to divide a number of the form abab...a


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board