Understanding A109598: The Search for Patterns in an Integer Sequence

[tuttlerice]

Homework Statement

An integer sequence has cropped up in research I'm doing, but I'm having trouble understanding it. A number n is on this integer sequence if there is no m>0 such that n+m is divisible by 6m-1, 6m+1, 8m-1 or 8m+1.

http://oeis.org/A109598

What I'm wondering is if there is some quick and easy way to ascertain whether a given number belongs on this list or not. It seems like each number would require a mini proof. For example, 5 is on the list. How do we know that there is *no m at all* such that 5+m is divisible by 6m-1, 6m+1, 8m-1 or 8m+1? How do we exhaust all possibilities for m?

It seems like there is a method here that I am missing.

Homework Equations

n+m=6m-1
n+m=6m+1
n+m=8m-1
n+m=8m+1

The Attempt at a Solution

I tried to write to the author of this sequence, David Wasserman, and have not heard back from him. It is possible the e-mail address I used is out of date, as his website is also quite out of date.

 

[Dick]

Homework Statement

An integer sequence has cropped up in research I'm doing, but I'm having trouble understanding it. A number n is on this integer sequence if there is no m>0 such that n+m is divisible by 6m-1, 6m+1, 8m-1 or 8m+1.

http://oeis.org/A109598

What I'm wondering is if there is some quick and easy way to ascertain whether a given number belongs on this list or not. It seems like each number would require a mini proof. For example, 5 is on the list. How do we know that there is *no m at all* such that 5+m is divisible by 6m-1, 6m+1, 8m-1 or 8m+1? How do we exhaust all possibilities for m?

It seems like there is a method here that I am missing.

Homework Equations

n+m=6m-1
n+m=6m+1
n+m=8m-1
n+m=8m+1

The Attempt at a Solution

I tried to write to the author of this sequence, David Wasserman, and have not heard back from him. It is possible the e-mail address I used is out of date, as his website is also quite out of date.

If 6m-1>n+m then none of those numbers can divide n+m. Solving 6m-1<=n+m, that inequality shows m<=(n+1)/5. So you only need to check those values of m. In the case of n=5 you only need to check m=1.

 

[tuttlerice]

Thanks again, Dick. Am I correct that the quickest, easiest test for any n is to see if either n-1 or n+1 divides either 5 or 7? If not, n goes on the list? True?

 

[tuttlerice]

Also, the original question posited on OEIS is whether or not the sequence is infinite. Am I correct that the sequence is indeed infinite because one cannot run out of numbers whose next-door-neighbors divide neither 5 nor 7?

 

[Office_Shredder]

tuttlerice, if that was true then 17 would be on the list, because 16 is not divisible by 5 or 7, and 18 is not divisible by 5 or 7

 

[tuttlerice]

Okay, I think I understand it now. Dick's method narrows it down to a finite number of m to check. To see if, say, 55 belongs on the list, see what (55-1)/7 is. It's appx. 7.714. So check values of m between 1 and 7. (55+1)/(6-1) is not whole. (55+1)/(6+1) is not whole. Aha, (55+1)/(8-1) is whole. So, 55 does not belong on the list. Even if it had not been the case that (55+1)/(6+1) is whole, there are only 7 numbers m to check on, which can be done reasonably quickly. The bigger the n, the more m there are to check, but it's still at least always a finite number of m.

Do I have this right, I hope?

 

[Dick]

Okay, I think I understand it now. Dick's method narrows it down to a finite number of m to check. To see if, say, 55 belongs on the list, see what (55-1)/7 is. It's appx. 7.714. So check values of m between 1 and 7. (55+1)/(6-1) is not whole. (55+1)/(6+1) is not whole. Aha, (55+1)/(8-1) is whole. So, 55 does not belong on the list. Even if it had not been the case that (55+1)/(6+1) is whole, there are only 7 numbers m to check on, which can be done reasonably quickly. The bigger the n, the more m there are to check, but it's still at least always a finite number of m.

Do I have this right, I hope?

Right. But (55+1)/(6+1) is actually whole too. Just a detail.

 

[tuttlerice]

Good point. Thanks again. I need to proofread myself more. It's a late New Years' Resolution.

 

[tuttlerice]

I'm not seeing why 61 and 81 are not included on this list? I'm not finding any whole number solutions.

For example, with 61:

divisibility by 6x-1: 62/5 63/11 64/17 65/23 66/29 67/35 68/41 69/47 etc.
divisibility by 6x+1: 62/7 63/13 64/19 65/25 66/31 67/37 68/38 69/49 etc.
divisibility by 8x-1: 62/7 63/15 64/23 65/31 66/39 67/47 etc.
divisibility by 8x+1: 62/9 63/17 64/25 65/33 66/41 etc.

I noticed there are never any numbers ending in 1, 4, 6 or 9 on the list. I understand 9 and 4, because when m=1, n+m will sum to a number ending in 0 or 5, which is divisible by 6(1)-1. I am not certain, however, that all numbers ending in 1 or 6 should be omitted from the list. I also think 51, 81, 56 and 126 might possibly belong on the list, at least according to a little program I wrote.

 

[Dick]

I'm not seeing why 61 and 81 are not included on this list? I'm not finding any whole number solutions.

For example, with 61:

divisibility by 6x-1: 62/5 63/11 64/17 65/23 66/29 67/35 68/41 69/47 etc.
divisibility by 6x+1: 62/7 63/13 64/19 65/25 66/31 67/37 68/38 69/49 etc.
divisibility by 8x-1: 62/7 63/15 64/23 65/31 66/39 67/47 etc.
divisibility by 8x+1: 62/9 63/17 64/25 65/33 66/41 etc.

I noticed there are never any numbers ending in 1, 4, 6 or 9 on the list. I understand 9 and 4, because when m=1, n+m will sum to a number ending in 0 or 5, which is divisible by 6(1)-1. I am not certain, however, that all numbers ending in 1 or 6 should be omitted from the list. I also think 51, 81, 56 and 126 might possibly belong on the list, at least according to a little program I wrote.

Better check your program. I don't think you are testing values of m that go high enough. 61+12 is divisible by 6*12+1 and 81+16 is divisible by 6*16+1.

 

[tuttlerice]

You're right. I've set it to search for values from 1 to n itself and now it works. I had it set to values from 1 to (n+1)/7 and I thought that should work, but I guess not.

Is there some principled reason anyone can see why numbers ending in 1 or 6 are never on the list?

Also, numbers that are powers are not on the list (e.g., no 3^4, no 2^7) except for 25, and no factorials are on the list other than 2.

I'm trying to see if there is a way to prove the list is infinite by finding some theoretical number that has to be on the list (such as, if n is on the list, n! is on the list, or n^2, or something), but this list seems to defy such relationships. It also defies arithmetic progressions (10 is on the list, 30 is on the list, but 50 is not on the list, etc.).

One principle that seems to hold with this list is that if n is on this list, (n+1)/7 is not whole.

 

[tuttlerice]

Other squares that belong on the list: 4900, 22500, 55225, 81225, 180625, 245025, 455625.
All divisible by 5.

 

[Dick]

You're right. I've set it to search for values from 1 to n itself and now it works. I had it set to values from 1 to (n+1)/7 and I thought that should work, but I guess not.

Is there some principled reason anyone can see why numbers ending in 1 or 6 are never on the list?

Also, numbers that are powers are not on the list (e.g., no 3^4, no 2^7) except for 25, and no factorials are on the list other than 2.

I'm trying to see if there is a way to prove the list is infinite by finding some theoretical number that has to be on the list (such as, if n is on the list, n! is on the list, or n^2, or something), but this list seems to defy such relationships. It also defies arithmetic progressions (10 is on the list, 30 is on the list, but 50 is not on the list, etc.).

One principle that seems to hold with this list is that if n is on this list, (n+1)/7 is not whole.

Didn't I give you an argument that said you should check all of the values up to (n+1)/5? That's exactly as far as you need to go. Why were you checking only up to (n+1)/7? And as to your other conjectures, I'm not sure. I haven't really given a lot of thought to it because it seems really hard. There are an awful lot of possible factors for an awful lot of numbers. Your idea of finding very large numbers that must be on the list seems sound. But I don't know how to do it. I'd suggest you correct your program and stretch to larger numbers and try to eliminate as many of the conjectures as you can. Do you mind if I ask why this problem is so interesting for you?