Author |
Topic: divisibility by 29 (Read 5041 times) |
|
Christine
Full Member
Posts: 159
|
 |
divisibility by 29
« on: Jul 22nd, 2013, 1:04pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
pex
Uberpuzzler
Gender: 
Posts: 880
|
|
Re: divisibility by 29
« Reply #1 on: Jul 22nd, 2013, 2:00pm » |
Quote Modify
|
on Jul 22nd, 2013, 1:04pm, 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,...
|
|
IP Logged |
|
|
|
Christine
Full Member
Posts: 159
|
|
Re: divisibility by 29
« Reply #2 on: Jul 22nd, 2013, 3:05pm » |
Quote Modify
|
How do you establish this?
on Jul 22nd, 2013, 2:00pm, pex wrote:
and the formulas for other primes other than 29, like 23, 31, etc.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: divisibility by 29
« Reply #3 on: Jul 22nd, 2013, 10:59pm » |
Quote Modify
|
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)
|
| « Last Edit: Jul 22nd, 2013, 11:18pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: divisibility by 29
« Reply #4 on: Jul 23rd, 2013, 2:38am » |
Quote Modify
|
on Jul 22nd, 2013, 3:05pm, 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!
|
|
IP Logged |
|
|
|
Christine
Full Member
Posts: 159
|
|
Re: divisibility by 29
« Reply #5 on: Jul 24th, 2013, 7:18pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: divisibility by 29
« Reply #6 on: Jul 24th, 2013, 11:28pm » |
Quote Modify
|
Hmm, it appears to hold for all numbers abab..a ; they're always divisible by between 318 to 372 of the first 1000 primes
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Christine
Full Member
Posts: 159
|
|
Re: divisibility by 29
« Reply #7 on: Jul 26th, 2013, 1:39am » |
Quote Modify
|
on Jul 24th, 2013, 11:28pm, 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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: divisibility by 29
« Reply #8 on: Jul 26th, 2013, 5:13am » |
Quote Modify
|
on Jul 26th, 2013, 1:39am, Christine wrote: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
|
| « Last Edit: Jul 26th, 2013, 5:17am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Christine
Full Member
Posts: 159
|
|
Re: divisibility by 29
« Reply #9 on: Jul 26th, 2013, 9:17am » |
Quote Modify
|
I'm sorry towr, I was wrong.
Thank you for posting your list
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: divisibility by 29
« Reply #10 on: Jul 26th, 2013, 12:51pm » |
Quote Modify
|
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
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Christine
Full Member
Posts: 159
|
|
Re: divisibility by 29
« Reply #11 on: Jul 26th, 2013, 4:29pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print